Dynamic programming — never doing the same work twice

Naive recursion that stops returning when you just slightly enlarge the input. This phenomenon has a fixed cause: the same argument is being computed repeatedly.

Dynamic programming is the technique for collapsing that repetition into one computation. It has a difficult name, but what it does is just "remember answers once computed".

What you'll learn in this chapter

• How to notice subproblem overlap
• The correspondence between memoization and tabulation; which to write in
• The two conditions for applicability
• Estimating complexity as state count × transition cost
• How to design states and transitions

Prerequisites

Builds on the recursion tree from Recursion and divide-and-conquer and big-O from Complexity.

Notice the overlap

In the Recursion and divide-and-conquer chapter, we saw that Fibonacci written by definition triggers 2.69 million calls for fib(30).

fib(3) appears twice, fib(2) three times. Same argument, same answer, yet we retrace each time.

This "same argument appearing multiple times in the recursion tree" is called subproblem overlap. That's the difference from divide-and-conquer. In merge sort, the left half and right half don't overlap. So remembering has no value.

Memoization — top-down, remembering as we go

Record answers in a table; on second occurrence, read from the table. The recursion form stays.

let memoCalls = 0;
function fibMemo(n: number, memo = new Map<number, number>()): number {
  memoCalls++;
  if (n <= 1) return n;
  const hit = memo.get(n);
  if (hit !== undefined) return hit; // Second call returns here
  const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, v);
  return v;
}

memoCalls = 0;
fibMemo(30);
console.log(`memoized fib(30) calls: ${memoCalls}`);
// memoized fib(30) calls: 59

2.69 million calls became 59. There are 31 kinds of n from 0 to 30, and each argument only has "initial computation" and "table lookup" once at most.

Exponential dropped to linear. The algorithm didn't change — the overlap was just collapsed.

Tabulation — bottom-up, in order

The same thing works by dropping recursion and filling from the small side up in order.

function fibTable(n: number): number {
  if (n <= 1) return n;
  const dp = new Array<number>(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

console.log(`fibTable(30) = ${fibTable(30)}`);
// fibTable(30) = 832040

They're the same thing, seen from opposite sides

	Memoization (top-down)	Tabulation (bottom-up)
Style	Recursion + a table	Fill in order with a loop
Range computed	Only needed subproblems	Every cell of the table
Stack	Stacks up to depth	Doesn't stack
Fits	Wide state; only some are used	All states used; order is clear

Write in memoization first. Adding three lines to naive recursion suffices, and the transition equation stays in the definition's shape — less error-prone. Switch to tabulation when depth becomes a problem, or when you know all states will be used.

Two conditions for applicability

Condition	Meaning	Failing example
Subproblem overlap	Same subproblem appears multiple times	Merge sort (left and right are separate data)
Optimal substructure	Combining optimal solutions of subproblems yields the optimal solution overall	Problems where a partial choice changes later options

Without overlap, remembering is meaningless. Without optimal substructure, the assembled answer isn't optimal. Just one of the two isn't dynamic programming.

Complexity is "state count × transition cost"

Dynamic programming's complexity comes from this product.

• State count = number of cells in the table
• Transition cost = how many other cells each cell references

Fibonacci has n states and each cell references 2, so O(n). A 2D example below has n × m states with constant transition, so O(n × m).

This estimation guides design. Adding a state grows the table by an entire dimension, so state proliferation directly affects complexity. Filter "does this really need to be in the state" up front.

Designing states and transitions

Consider counting ways to climb n steps, taking 1 or 2 at a time.

Design is three decisions.

1. State — dp[i] = number of ways to reach step i
2. Transition — reach step i from i-1 with one step or from i-2 with two. So dp[i] = dp[i-1] + dp[i-2]
3. Initial value — dp[0] = 1 (doing nothing is one way)

function climbWays(n: number): number {
  const dp = new Array<number>(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 0);
  }
  return dp[n];
}

console.log(`climbWays(5) = ${climbWays(5)}`);   // climbWays(5) = 8
console.log(`climbWays(10) = ${climbWays(10)}`); // climbWays(10) = 89

Write transitions in the form "from where can this state be reached". Writing "where can this state go to" fills the same table, but the "from" form makes the initial value's location clearer.

A 2D table example

The longest sequence that appears in two strings, not necessarily contiguous — the longest common subsequence. It's the calculation underneath diff displays.

• State — dp[i][j] = answer for the first i characters of a and the first j of b
• Transition — if trailing characters match, dp[i-1][j-1] + 1; if not, the larger of "drop a's tail" and "drop b's tail"

function lcsLength(a: string, b: string): number {
  const dp: number[][] = Array.from({ length: a.length + 1 }, () =>
    new Array<number>(b.length + 1).fill(0),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

console.log(lcsLength("abcde", "ace"));      // 3
console.log(lcsLength("kitten", "sitting")); // 4

State count n × m, constant transition, so O(n × m).

Keep only the previous row

In the code above, dp[i][j] references only dp[i-1][*] and dp[i][j-1]. Two rows suffice.

function lcsLengthTwoRows(a: string, b: string): number {
  let prev = new Array<number>(b.length + 1).fill(0);
  for (let i = 1; i <= a.length; i++) {
    const cur = new Array<number>(b.length + 1).fill(0);
    for (let j = 1; j <= b.length; j++) {
      cur[j] = a[i - 1] === b[j - 1]
        ? prev[j - 1] + 1
        : Math.max(prev[j], cur[j - 1]);
    }
    prev = cur;
  }
  return prev[b.length];
}

Space drops from O(n × m) to O(m). Time doesn't change.

There's a cost. You can't recover the path in this two-row version. If you need "which characters are common", not just "length", keep the full table. Diff display's purpose is path recovery, so naive compression breaks it. (There's a technique that combines with divide-and-conquer to recover in linear space, but implementation is heavier.)

Difference from greedy

Greedy picks the locally best choice, no backtracking. When it works, it's faster than dynamic programming and the code is shorter.

The divide is whether locally optimal choices lead to a globally optimal answer. Where they do, greedy is correct; where they don't, dynamic programming is needed.

Coin change is the clear example. Japanese denominations (1, 5, 10, 50, 100, 500 yen) let greedy from largest down give minimum count. But with coins of 1, 3, 4 yen making 6, greedy gives 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2.

A change in "input" (the coin set) breaks greedy's correctness. Adopting greedy requires being able to say "why local optimum equals global optimum on this problem". If you can't, pick dynamic programming.

Decision procedure

1. Write naive recursion first. Get a working form up
2. Look for the same argument in the recursion tree. If none, DP isn't the tool
3. Memoize. Just add a table
4. Count state count × transition cost and confirm it fits
5. If depth is a problem or all states are used, switch to tabulation
6. If space is a problem, keep only the previous row. But don't compress if you need path recovery

Step 2 is the most important. DP isn't a tool for "speeding up any slow recursion". It only works when there's overlap. Slow with no overlap has a different cause.

Common misconceptions

"DP is a difficult algorithm." — Not an algorithm — a technique. The core is "put answers in a table"; the hard part is designing states and transitions.

"Memoization and DP are different." — Memoization is one way of writing DP. Top-down vs. bottom-up — same table gets filled.

"Tabulation is faster." — Same order. Tabulation wins on constant factors by dropping function calls, but it may fill unneeded subproblems and lose. If the state space is wide and only some are used, memoization finishes faster.

"Recursion is slow, so memoize." — Slowness comes from overlap, not recursion. Memoizing recursion without overlap slows things down by adding a table.

"Holding more state is safer." — Adding a state grows the table by a dimension. State count directly affects complexity, so trim to the minimum needed.

Exercises

Q1. You memoized a slow recursive process and it didn't speed up. What to verify?

Answer and explanation

Answer: Verify that the recursion tree actually has the same argument appearing multiple times.

Memoization works only when overlap exists. Not working means one of these:

• No overlap — like divide-and-conquer where subproblems are disjoint. Memoization then slows things down by adding a table
• Argument doesn't match as a key — passing objects or arrays as-is treats identical contents as different. Normalize to strings or numbers
• Memo recreated per call — passing a new Map on each recursion means records don't carry over

Triage by counting calls. If count doesn't change with memoization, it's items 2 or 3. If count drops but time doesn't, per-call processing is heavy — the cause is outside memoization.

Q2. You wrote a "choose products within budget" (a.k.a. knapsack) DP and ran out of memory. State is three things: "which product so far", "budget used", "items selected". What now?

Answer and explanation

Answer: See if state can be reduced first. Removing one dimension changes orders of magnitude.

State count is the product of the three. 1,000 products × 1,000,000 budget × 100 items = 100 billion cells — no code will fit.

Consider in order.

1. Truly needed? — if "items selected" isn't in the answer condition, remove it. Re-read the constraints
2. Coarser granularity? — budget need not be in yen; per-100-yen buckets cut state count by 100
3. Can a dimension be dropped? — "which product so far" often only references the immediate previous, so keeping just two rows removes it

The third is the biggest impact. In this example, 500× reduction. But path recovery becomes impossible, so if "which products were chosen" is in the answer, this doesn't work. Then record choices in another light form, or split the table into staged processing.

Doubting the design comes first; implementation tricks come after. Three states is enough reason to suspect a misread of the problem.

Q3. For "shortest path" problems, how do you decide between DP and BFS?

Answer and explanation

Answer: By whether state transitions have cycles.

DP requires that subproblems be ordered. Computing dp[i] requires dp[i-1] to be settled. This ordering is possible when state transitions move in one direction — that is, when there are no cycles.

• No cycles (advancing stages, consuming characters) → DP. Table can be filled in order
• Cycles present (boards or maps that can revisit) → BFS (only when edge weights are equal; otherwise Dijkstra). No order, so no table filling

Topological sort from the Graphs and traversal chapter is the bridge. For an acyclic directed graph, order can be established, and filling the table in that order is DP.

In practice, both can point to the same thing. For an acyclic graph with equal edge weights, BFS distances and DP-filled tables coincide. Choose by which is more natural for the state's ordering.

Summary

• DP is a technique, not an algorithm. "Remember answers once computed"
• It works when there's subproblem overlap. Judge by whether the same argument appears repeatedly in the recursion tree
• Memoization (top-down) and tabulation (bottom-up) are two sides of the same thing. Write memoization first
• Conditions: overlap and optimal substructure. Only one doesn't do it
• Complexity is state count × transition cost. Adding a state grows the table by a dimension
• Design is three things: state, transition, initial value. Write transitions "from where"
• Keeping only the previous row drops space by a dimension. But you can't recover the path
• Difference from greedy: whether local optimum reaches global optimum. Can't say why → pick DP
• Not a tool for speeding up any slow recursion. No overlap → doesn't work

Related references

• Complexity — Foundation for estimating state count × transition cost
• Binary search — Divide-and-conquer "only one half solved" form — the contrast where holding a table is pointless because there's no overlap

What to read next

• Array scanning patterns — Another tool for reducing nested loops to a single pass without a table
• Recursion and divide-and-conquer — Contrast with non-overlapping recursion