4.22 — Dynamic Programming

Compute the 45th Fibonacci number with the obvious recursion and your laptop takes about thirty seconds. Compute the 50th and it takes about six minutes. Compute the 90th and you will not live to see it.

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);        // ← two calls per level → 2ⁿ
}

The recursion is correct. The problem is that it computes the same values over and over. fib(45) calls fib(43) twice, fib(42) three times, fib(41) five times — the counts are themselves Fibonacci numbers — and fib(1) gets computed about 1.8 billion times.

The recursion tree for fib(5). The identical subtrees are the waste. Note that this is not a "slow implementation" problem — the tree genuinely has 2ⁿ nodes, and no amount of micro-optimisation fixes an exponential shape. The fix has to change the shape.

Dynamic programming is the fix, and it is one idea: when subproblems repeat, solve each one once and remember the answer. That is the whole of it. Everything else is technique for spotting when it applies and choosing how to store the answers.

1. The two conditions

DP applies when both of these hold. If either fails, it is the wrong tool.

Overlapping subproblems. The same subproblem is needed more than once. Fibonacci has this; merge sort does not (its two halves are disjoint, so nothing repeats, which is why it is divide and conquer and not DP).

Optimal substructure. The best answer for the whole problem is built from the best answers to its subproblems. The shortest path from A to C through B is the shortest A→B plus the shortest B→C. This sounds obvious and is not always true: the longest simple path does not have it, because the longest path from A to B plus the longest from B to C may reuse vertices and stop being a valid path at all. That is precisely why longest-simple-path is NP-hard while shortest-path is easy.

2. Is it DP, or greedy, or plain recursion?

This is the question that causes the most trouble, so here is a decision you can actually run.

Step 1 — what is the question asking for?

the question asks for	what it is
every arrangement, all combinations, list them	backtracking (4.18)
how many ways, or the best value	DP or greedy — go to step 2
whether something exists	DP, usually, or a search

Enumerating and optimising are different jobs. Combination Sum asks for every combination, so it is backtracking. Coin Change asks for the fewest coins, so it is DP. The two problems look almost identical and the answer to "which technique" comes entirely from that one word.

Step 2 — is the obvious greedy choice provably safe?

Greedy takes the locally best option and never reconsiders. It works only when you can prove that the local choice is part of some optimal answer. DP exists precisely because that proof usually fails.

The fastest test is to hunt for a counterexample for thirty seconds. Take the greedy rule and try to break it.

• Coin Change with coins [1, 3, 4], target 6. Greedy takes the biggest coin first: 4, then 1, then 1 — three coins. The right answer is 3 + 3, two coins. Greedy fails, so it is DP.
• Coin Change with coins [1, 5, 10, 25], target 30. Greedy gives 25 + 5. Correct. Real currency systems are designed so greedy works, which is exactly why the intuition misleads people.
• Jump Game — can you reach the end? Greedy tracking the furthest reachable index works, and can be proved. Greedy, not DP.

If you find a counterexample, it is DP. If you cannot find one in thirty seconds and you also cannot prove the rule, write the DP — it is never wrong, only slower.

Step 3 — the structural tells.

DP is very likely when:

• A choice now restricts choices later. Robbing this house means you cannot rob the next one. That dependency is what greedy cannot see.
• The same subproblem shows up on several branches. Draw two levels of the recursion tree; if you write the same call twice, that is overlapping subproblems.
• The constraints are small in a suspicious way. n ≤ 1000 with a target ≤ 10^4 is someone telling you an O(n \times target) table is expected.
• The answer counts things. "How many ways" is almost always DP, because ways add up over subproblems.

Greedy is very likely when:

• Sorting the input first makes the choice obvious (4.25).
• Each step consumes a resource and never affects what is available later.
• The problem is about intervals, scheduling, or "how few of X do I need".

The honest fallback, and it is worth saying in an interview: "I will write the DP because it is always correct here, and then check whether a greedy rule can be proved — if it can, I will simplify." Greedy that cannot be justified is a guess, and a guess that passes the sample tests is worse than a correct O(n^2).

3. The four forms, and how to convert between them

The same DP can be written four ways. They compute identical answers and differ only in how the results are stored. Knowing the conversions mechanically is what stops the four looking like four separate skills.

form	shape	space	when
1. memoised recursion	top-down, cache on the parameters	O(\text{states}) + stack	deriving it; sparse state spaces
2. full table	bottom-up, one array or grid	O(\text{states})	the default answer
3. rolling array	keep only the rows you read	O(\text{one row})	2-D reading one previous row
4. a few variables	keep only the cells you read	O(1)	1-D reading a fixed window

Form 1 → form 2. The parameters of the recursion become the dimensions of the table. The base cases become the initial values. The recursive calls become table reads — and the loop must run in an order that guarantees those cells are already filled. Reverse the direction the recursion travelled: if f(i) calls f(i-1), the loop counts upwards; if f(i) calls f(i+1), it counts downwards.

Form 2 → form 3. Look at the recurrence and list which rows it reads. If dp[i][j] only ever reads row i-1, you need two rows, not n. Keep prev and curr and swap them at the end of each row.

Form 3 → form 4. If a single row's recurrence only reads a fixed number of cells, replace the row with that many variables.

The trap in form 3, and it is the classic one. When you collapse to a single array updated in place, the loop direction suddenly matters:

# 0/1 knapsack — each item used ONCE → iterate the capacity DOWNWARDS
for w in range(capacity, weight - 1, -1):
    dp[w] = max(dp[w], dp[w - weight] + value)

# unbounded knapsack — items reusable → iterate UPWARDS
for w in range(weight, capacity + 1):
    dp[w] = max(dp[w], dp[w - weight] + value)

Those two loops differ only in direction, and that direction is the entire difference between "use each item once" and "reuse freely".

Going downwards, dp[w - weight] still holds the value from before this item was considered, so the item is used at most once. Going upwards, dp[w - weight] may already include this item, so it can be used again.

When you meet a one-line DP whose loop runs backwards and cannot see why, this is almost always the reason. 4.23 and 4.24 use it repeatedly.

Which form to write in an interview. Derive with form 1, because the recursion is the part you can reason about. Then say "this is O(\text{states}) space; I can make it bottom-up and roll the array to O(\text{row})" and write that if they want it. Showing the ladder is worth more than landing on the tightest version immediately.

4. Memoisation: the smallest possible change

Add a cache. The recursion stays exactly as it was.

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;                    // (1)
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);                                     // (2)
  return result;
}

1. Already computed — return it, and do not recurse. This line is what prunes the entire duplicate subtree.
2. Store before returning.

Now every distinct value of n is computed exactly once, so there are n computations of O(1) work each: O(n) time, O(n) space. From 2^n to n by adding two lines.

This is called top-down DP, or memoisation. Its great virtue is that you write the plain recursion first — which is usually the easy part — and then add the cache. You never have to figure out the right order to fill anything in, because the recursion discovers the order for you.

The cache key must be exactly the parameters that vary. If your recursion takes (index, remainingBudget), the key is the pair, not just the index. Getting this wrong gives silently wrong answers, because a cached result computed under one budget gets returned under another.

5. Tabulation: bottom-up, no recursion

Tabulation flips the direction: instead of asking for f(n) and recursing down, start at the base cases and build upward.

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

1. One slot per subproblem.
2. The base cases, written in directly.
3. The loop order must guarantee that everything a cell depends on is already filled. Here dp[i] needs i-1 and i-2, both smaller, so ascending order works. In 2-D problems this ordering question is the main thing to get right.

O(n) time, O(n) space, no recursion, no stack overflow, and a smaller constant factor because there are no function calls and no hash lookups.

Then the space optimisation. dp[i] only ever reads the previous two cells, so the array is unnecessary:

function fibFast(n: number): number {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) [prev, curr] = [curr, prev + curr];   // (1)
  return curr;
}

1. Two variables rolling forward. O(n) time, O(1) space.

This "keep only the rows you actually read" move is general and is asked constantly. Any 2-D DP whose recurrence reads only the previous row can drop from O(nm) space to O(m). Any 1-D DP reading a fixed window drops to O(1).

Choosing between top-down and bottom-up:

	Memoisation (top-down)	Tabulation (bottom-up)
Write it from	the plain recursion	the recurrence and an ordering
Fill order	discovered automatically	you must work it out
Computes	only reachable subproblems	all of them
Risk	stack overflow when deep	none
Space optimisation	hard	easy (roll the arrays)

The practical advice: derive with memoisation, ship with tabulation if the space optimisation matters. And when the state space is huge but only a sparse part is reachable, memoisation is genuinely better, because tabulation would fill a table full of answers nobody asks for.

6. The method: five questions that produce the recurrence

The hard part of DP is never the code. It is defining the state. Answer these five in order and the code is mechanical.

1. What is the state? The smallest set of facts that determines the rest of the problem. Write it as the parameters of a function f(...) and say in English what f returns. "f(i) = the largest sum of a non-adjacent subsequence of nums[0..i]." Vague state definitions are the cause of almost every DP failure.

2. What is the choice at each state? Usually two or three: take this item or skip it, match these characters or delete one, cut here or do not.

3. What is the recurrence? Combine the choices, taking the best. f(i) = max(f(i-1), f(i-2) + nums[i]) — either skip element i and keep the best up to i−1, or take it and add the best up to i−2, since adjacency is forbidden.

4. What are the base cases? The states small enough to answer directly. Off-by-one errors live here.

5. What order fills the table? Every state must be computed after everything it depends on.

Worked end to end on the house robber problem — you cannot rob two adjacent houses, maximise the total:

function rob(nums: number[]): number {
  let skip = 0, take = 0;                          // (1)
  for (const value of nums) {
    const newTake = skip + value;                  // (2)
    const newSkip = Math.max(skip, take);          // (3)
    skip = newSkip; take = newTake;                // (4)
  }
  return Math.max(skip, take);
}

1. take is the best total where the previous house was robbed; skip where it was not. Two rolling numbers replace the whole table.
2. Robbing this house requires that the previous one was skipped.
3. Skipping this house allows either previous state, so take whichever was better.
4. Assign together so neither overwrites the other before it is read — the same care as the swap in Chapter 4.7's list reversal.

O(n) time, O(1) space, and the whole derivation was answering the five questions.

7. The classical patterns worth recognising on sight

Most DP problems are one of about eight shapes. Recognising the shape gives you the state definition, which is 90% of the work.

Linear, decide per element. State is f(i), the answer considering the first i elements. House robber, maximum subarray, climbing stairs, decode ways, longest increasing subsequence.

Knapsack — two dimensions, one is a resource. State is f(i, capacity). The choice is take or skip, and taking reduces the capacity. 0/1 knapsack takes each item at most once; unbounded knapsack allows repeats, and the only difference in the code is the loop direction, which is a favourite follow-up. Coin change, partition-equal-subset and target-sum are all this.

Two sequences — a grid over both. State is f(i, j), comparing prefixes of two strings. Edit distance, longest common subsequence, regular-expression matching. The recurrence always has a "characters match" branch and one branch per allowed edit.

Intervals — work outward from small ranges. State is f(i, j) over a contiguous range, and the recurrence tries every split point k inside it. Matrix chain multiplication, burst balloons, palindrome partitioning. These are O(n^3) because there are n^2 states and each tries n splits.

Grid paths. State is f(row, col) and you arrive from above or from the left. Unique paths, minimum path sum, maximal square.

Digit DP, bitmask DP, tree DP. Rarer. Bitmask DP encodes a subset of up to about 20 items as an integer, giving 2^n states — the travelling salesman problem in O(2^n n^2) instead of O(n!). Tree DP computes each node's answer from its children in post-order, which you already met in Chapter 4.13.1.

Longest increasing subsequence deserves its own note, because it has two solutions at different complexities and the faster one is genuinely surprising. The DP version is O(n^2): f(i) is the longest increasing subsequence ending at i, and you scan every earlier j. The O(n \log n) version maintains an array where position k holds the smallest possible tail of an increasing subsequence of length k+1, and binary-searches each new element into it. That array is not itself a valid subsequence — only its length is meaningful — which is the part everyone gets wrong when explaining it.

8. DP is shortest path on a DAG

This connection makes several things click at once.

Every DP problem is a graph. The states are vertices, the choices are edges, and the recurrence is edge relaxation. Because a state only ever depends on strictly smaller states, the graph has no cycles — it is a DAG. And Chapter 4.19.3's last table said that shortest paths on a DAG are solved by relaxing edges in topological order in O(V+E).

That is exactly what tabulation is: the loop order is the topological order, and each cell update is a relaxation.

Two things follow immediately.

The complexity formula. Time is (number of states) × (work per state). Edit distance has n \times m states and O(1) work each, so O(nm). Interval DP has n^2 states and O(n) work each, so O(n^3). Count the states and count the transitions — that is the whole analysis, and it is far more reliable than trying to reason about the recursion.

Why the loop order matters and how to get it right. Ask which states each cell reads, and make sure they come earlier in the loop. That is why unbounded knapsack iterates capacity ascending (so an item can be reused within the same pass) and 0/1 knapsack iterates it descending (so it cannot). One reversed loop is the entire difference between the two problems.

What the interviewer will push on

"How did you know this was a DP problem?" Two conditions, named: overlapping subproblems and optimal substructure. Then the practical tell — you drew the recursion tree and saw a repeated node. Answering "it felt like one" is what they are screening against.

"What is the state, and what does your function return?" Say it as a full English sentence before writing code: "f(i, c) is the maximum value obtainable using the first i items with capacity c remaining." Candidates who cannot state this cleanly write recurrences that are subtly wrong.

"What is the time and space complexity?" States times work per state. Then volunteer the space optimisation: which rows does the recurrence actually read, and can the table be rolled down to one row or two variables?

"Convert your memoised solution to bottom-up." They want to see that you can work out the fill order, which means knowing what each cell depends on. The follow-up is what you gain — no stack overflow, smaller constants, and the space optimisation becomes possible.

"Your 0/1 knapsack loops capacity descending. Why?" Because ascending would let the same item be picked twice in one pass, which is the unbounded problem. One loop direction is the entire difference, and knowing that is a strong signal.

"What if the answer is not the count but the actual items chosen?" Keep a parent or choice array, or walk the finished table backwards from the answer cell, reversing the recurrence to see which branch produced each value. Same idea as reconstructing the shortest path in Chapter 4.19.3.

One thing to volunteer: say that DP is shortest path on a DAG of states, and that the loop order is the topological order. It explains both the complexity formula and why the loop direction matters, and it connects the topic to the graph chapter rather than leaving it as a bag of recipes.

Recall

• DP applies when two conditions hold: overlapping subproblems and optimal substructure. Longest simple path fails the second, which is why it is NP-hard while shortest path is not.
• Memoisation is the plain recursion plus a cache keyed on exactly the varying parameters; the fill order is discovered for you.
• Tabulation starts at the base cases and needs you to work out an order where every cell's dependencies are already filled — then the space optimisation falls out: keep only the rows the recurrence actually reads.
• The method is five questions: state · choice · recurrence · base cases · fill order. Say the state as an English sentence before writing code.
• Complexity = number of states × work per state. Count both.
• DP is shortest path on a DAG of states: states are vertices, choices are edges, and the loop order is the topological order. This is why 0/1 knapsack loops capacity descending and unbounded loops ascending.

Self-test: Why is naive Fibonacci 2^n and not n^2? · What must the memo key contain, and what breaks if it is missing a parameter? · Roll a 2-D DP that reads only the previous row down to O(m) space · Why does the loop direction alone separate 0/1 from unbounded knapsack? · Explain what the array in the O(n \log n) longest-increasing-subsequence solution actually holds.

Next: 4.23 starts the dynamic programming problems with the one-dimensional ones, where the state is a single index and the whole skill is saying out loud what that index means.