Dynamic programming — patterns over magic

Dynamic programming has a reputation as the hardest topic in interviews. Most of that reputation is undeserved. DP isn't a separate algorithm; it's a recipe.

A problem is solvable by DP if it has two properties:

Optimal substructure. The optimal answer to size n depends on optimal answers to smaller sizes. (If you know fib(n-1) and fib(n-2), you know fib(n).)

Overlapping subproblems. The same smaller problems get computed multiple times across the recursion tree. (fib(n-3) shows up under both fib(n-1) and fib(n-2).)

When both properties hold, cache the smaller answers. That's DP. Recursion + memoisation.

The naive recursion has exponential runtime because of the recomputation. The memoised version has linear (or polynomial) runtime because each subproblem is solved exactly once.

Classical DP problems and the state shape:

Fibonacci — dp[n] = answer for size n. 1D state.
Climbing stairs (count distinct paths) — dp[n] = ways to reach step n. 1D.
Coin change (min coins for amount) — dp[a] = min coins for amount a. 1D.
Longest common subsequence — dp[i][j] = LCS of first i chars of A and first j chars of B. 2D.
Edit distance — dp[i][j] = edits to transform first i chars of A into first j chars of B. 2D.
Knapsack (maximise value within weight limit) — dp[i][w] = max value using first i items with weight budget w. 2D.

The state shape (1D, 2D, etc.) usually drops out of the problem statement. Identify what the smaller problem depends on. If just one parameter — 1D. If two — 2D.

DP is pattern recognition plus careful state design. The patterns repeat; once you've coded ten DP problems, the eleventh is recognisable.

Two ways to write any DP problem. Same answer. Same complexity. Different code shape and different memory characteristics.

Top-down (memoised recursion) — write the recursion the way the problem reads. Decorate with @lru_cache to cache results.

@lru_cache(maxsize=None)
def solve(i):
    if base_case(i):
        return base_value(i)
    return min(solve(i-1), solve(i-2)) + cost[i]

Bottom-up (iterative DP) — build a 1D or 2D array, fill it in dependency order with explicit loops.

dp = [0] * n
dp[0] = base_0
dp[1] = base_1
for i in range(2, n):
    dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
return dp[n-1]

When to pick which:

Top-down is easier to write. The code reads as the problem statement. lru_cache handles the memoisation. You don't have to think about iteration order — recursion handles dependency order automatically.

Bottom-up is easier to optimise. Once you've solved with top-down and confirmed correctness, you can rewrite as iterative. Often you can drop space — if dp[i] only depends on dp[i-1] and dp[i-2], you only need two variables, not the full array. Constant space instead of linear.

Bottom-up has no recursion limit. For very deep DP problems (n > 5000), top-down with @lru_cache hits Python's recursion ceiling unless you raise it. Bottom-up has no such issue.

My default — start top-down. Once it works, decide if bottom-up is worth the conversion (deeper-than-stack input, memory optimisation, micro-perf needed).

The transformation is mechanical. Identify the recursion's dependencies (i depends on i-1 and i-2). Write a loop in dependency order (from smallest i upward). Read each value from the array instead of recursing.

If you understand coin change, you understand 80% of DP problems. The other 20% are variations on the same theme.

Problem — given coin denominations [1, 2, 5] (or whatever) and a target amount (say 11), return the minimum number of coins to make exactly that amount. Or -1 if impossible.

State — dp[a] = minimum coins to make amount a.

Transition — dp[a] = min(dp[a - c] + 1 for c in coins if c <= a). For each coin c that doesn't exceed a, the answer is 1 (use c) plus the optimal answer for the remaining amount (a - c). Take the min across all coins.

Base case — dp[0] = 0 (zero coins to make zero amount). All other dp[a] start at infinity (unreachable) and get updated to actual values as we fill the table.

Look at the snippet. We allocate dp of size amount+1, initialised with [0] for amount 0 and inf elsewhere. The outer loop is over amounts 1 to target. The inner loop is over coins. We update dp[a] using the transition.

O(amount * len(coins)) time. O(amount) space.

Return — dp[amount] if it's still inf (impossible), -1; otherwise dp[amount].

Variations on the same shape:

Coin change II — count distinct ways to make the amount. Same state, different transition (sum, not min).

Climbing stairs (1 or 2 steps at a time) — coin change with coins=[1,2] and a count transition.

Edit distance — 2D state (one dim per string). Transition uses three operations (insert, delete, replace) instead of one.

Knapsack — 2D state. Transition picks 'include this item' vs 'skip this item'.

Learn the shape on coin change. Variations are tweaks.

DP fails when the state is fuzzy. The most reliable cure is to define your state as one English sentence before writing any code.

'dp[i] is the minimum number of coins to make exactly amount i.'

If you can write that sentence cleanly — concise, unambiguous, parameterised by your indices — you have a state. The transitions and base cases tend to follow.

If you can't write the sentence, your state is wrong. Common failure modes:

The sentence has 'or' or 'and' joining two ideas. 'dp[i] is the minimum coins OR -1 if impossible.' The disjunction is a smell — usually the right state separates these. Often you encode 'impossible' as infinity and check at the end.

The sentence requires a second dimension. 'dp[i] is the minimum coins to make i, given that the last coin used was c.' The second 'given that' tells you the state needs another index. dp[i][c].

The sentence is silent on what 'minimum' means. 'dp[i] is the path through the array.' Path optimising what? The cost? The count? The sum? Be specific.

For harder DPs (longest common subsequence, edit distance, knapsack), the sentence has two indices. 'dp[i][j] is the LCS of the first i characters of A and the first j characters of B.' Now transitions involve dp[i-1][j], dp[i][j-1], dp[i-1][j-1] depending on whether A[i-1] == B[j-1].

Write the sentence. Then the loop. Then the transition. Then test on a tiny input.

My rule — five minutes on the sentence saves an hour of debugging. The hardest part of DP isn't the code; it's stating the problem correctly.

End of Day 27. DP done.

What we covered.

Morning, DP framed simply — it's recursion + memoisation when the problem has optimal substructure and overlapping subproblems. Not magic. A recipe.

Midday, top-down vs bottom-up. Same answer, different code shape. Top-down is easier to write (recursion + lru_cache). Bottom-up is easier to optimise (loops + array, often constant space). Start top-down; convert if needed.

Afternoon, coin change as the gateway problem. State, transition, base case. The shape generalises to most other 1D and 2D DPs.

Evening, the most reliable DP technique — define the state in one English sentence before coding. If you can't write the sentence, your state is wrong. Five minutes on the sentence saves an hour of debugging.

A broader theme. DP problems are pattern-recognition problems. The patterns are limited (linear DP, grid DP, interval DP, tree DP, bitmask DP) and the variations on each pattern are predictable. Solve fifteen well-chosen DP problems and the eleventh is recognisable; the fifteenth is comfortable.

Tomorrow, Day 28, week four wrap. The 8 patterns that solve most leetcode mediums. The 20-problem study list. How I think during interviews. Then we exit DSA territory and head into the data stack.

See you in the morning.