Dynamic Programming

Definition

Dynamic programming solves a problem by breaking it into smaller subproblems, solving each subproblem once, and storing its answer so it never has to be recomputed. It applies when a problem has two properties: overlapping subproblems, meaning the same smaller subproblem is needed multiple times, as in naive recursive Fibonacci, where fib(3) is computed repeatedly while computing fib(6), and optimal substructure, meaning an optimal solution to the whole problem can be built from optimal solutions to its subproblems. Without both properties, memoizing answers either does nothing useful because subproblems never repeat, or gives an incorrect result because subproblem answers cannot be combined into the overall answer. There are two common ways to implement dynamic programming. Top-down, or memoization, keeps the natural recursive structure of the problem but caches each subproblem's result the first time it is computed, typically in an object, Map, or array, and returns the cached value immediately on later calls instead of recursing again. Bottom-up, or tabulation, instead builds a table of subproblem answers iteratively, usually starting from the smallest subproblems, the base cases, and filling in larger ones in order, so that every value the table needs already exists by the time it is used. Tabulation avoids recursion overhead and stack depth limits, while memoization is often more direct to write since it mirrors the recursive definition of the problem.

Examples

function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}
fibMemo(30); // 832040, computed in O(n) calls instead of exponentially many

function fibTable(n) {
  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}
fibTable(10); // 55

function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
minCoins([1, 3, 4], 6); // 2 (3 + 3)

Key takeaways

• Dynamic programming needs overlapping subproblems and optimal substructure; both must hold.
• Top-down memoization keeps the recursive shape of the problem and caches results as they are computed.
• Bottom-up tabulation fills in a table iteratively from base cases up, avoiding recursion.
• A cache hit reuses an already-solved subproblem instead of recomputing it, which is what turns exponential recursion into polynomial time.

Where you see this

• Computing edit distance or similarity between two strings, as used in spell checkers and diff tools.
• Finding the optimal way to cut a resource, such as minimum coins for change or maximum value in a knapsack of limited capacity.
• Sequence alignment problems in bioinformatics that compare DNA or protein sequences.
• Caching expensive pure function results in application code so repeated calls with the same arguments are instant.