Dynamic programming basics

What you'll learn

What dynamic programming (DP) is, how to spot overlapping sub-problems, and how to speed up recursion with memoization and with a bottom-up table.

Why it matters

Many problems (shortest routes, best prices, text comparison) can be solved by combining answers to smaller problems. DP turns solutions that would take years into ones that take milliseconds, and it is a favourite in interviews.

Explanation

Recall the naive Fibonacci from the recursion lesson: fib(n) = fib(n-1) + fib(n-2). It calls fib(3) many times when computing fib(6). The number of calls roughly doubles with each step: O(2 to the n).

Dynamic programming fixes this by never solving the same sub-problem twice. It applies when a problem has:

1. Overlapping sub-problems: the same smaller problems come up repeatedly.
2. Optimal substructure: the answer is built from answers to smaller problems.

Two styles:

• Memoization (top-down): keep the recursive code, but store each result in a map the first time and reuse it. Add a cache to the function.
• Tabulation (bottom-up): fill a table from the smallest case upward with a loop. No recursion, so no stack overflow.

With either, Fibonacci drops from O(2 to the n) to O(n).

Example

Step-by-step walkthrough

1. fibSlow(20) returns 6765, but needs 21891 calls because it recomputes the same values.
2. fibMemo(20) also returns 6765, but each value is computed once and stored, so it needs only 39 calls.
3. fibTable(50) fills a table from the bottom with a simple loop. It returns 12586269025 instantly. The slow version would never finish.
4. Climbing stairs: the ways to reach step i are the ways to reach i-1 (then take one step) plus the ways to reach i-2 (then take two). That is exactly the Fibonacci pattern, so climb(5) is 8.
5. Spotting that a new problem has the same shape as one you know is the main DP skill.

Try it yourself

Change 20 to 30 in fibSlow and notice how the number of calls explodes, while the memoized version barely grows.

MemoizationJavaScript

Editable codelet calls = 0; function fibSlow(n) { calls++; if (n < 2) return n; return fibSlow(n - 1) + fibSlow(n - 2); } let memoCalls = 0; function fibMemo(n, memo = {}) { memoCalls++; if (n < 2) return n; if (memo[n] !== undefined) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; } console.log(fibSlow(20), "calls:", calls); console.log(fibMemo(20), "calls:", memoCalls);

Run ResetCopyCtrl+Enter to run

Common mistakes

• Using DP where sub-problems do not overlap. Then plain recursion is enough.
• Not sharing the cache between recursive calls.
• Wrong base cases in the table, which shifts every later answer.
• Storing too much. Sometimes you only need the last two values, not the whole table.

Quick quiz

Summary

• DP solves each sub-problem once and reuses it.
• Memoization caches recursive calls; tabulation fills a table.
• It turns exponential solutions into linear ones when sub-problems overlap.

You finished the DSA track. Try the practice exercises to lock it in.

let calls = 0;
function fibSlow(n) {
  calls++;
  if (n < 2) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

let memoCalls = 0;
function fibMemo(n, memo = {}) {
  memoCalls++;
  if (n < 2) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

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

// Climbing stairs: how many ways to climb n steps taking 1 or 2 at a time?
function climb(n) {
  const ways = [1, 1];
  for (let i = 2; i <= n; i++) {
    ways[i] = ways[i - 1] + ways[i - 2];
  }
  return ways[n];
}

console.log(fibSlow(20), "calls:", calls);
console.log(fibMemo(20), "calls:", memoCalls);
console.log(fibTable(50));
console.log(climb(5));