05 — Dynamic Programming¶

DP is the topic that separates “can code” from “can think.” It is not memoization or tabulation — those are implementation styles. DP is the discovery that an optimization problem has overlapping subproblems and optimal substructure, and that you can therefore solve it in polynomial time instead of exponential. This file walks you through the mental model, the two implementation styles, and the 20 canonical problems that show up in nine out of ten studies that ask DP.

The DP mental model (memorize this)¶

Every DP problem answers three questions in order. If you cannot answer them, you do not have a DP yet.

State — What is the smallest set of variables that fully describes a subproblem? (e.g., dp[i] = LIS ending at i; dp[i][w] = knapsack value using first i items with capacity w)
Transition — How does the answer at one state depend on smaller states? (e.g., dp[i] = max(dp[j]+1) for j<i, nums[j]<nums[i])
Base case + order — Where does recursion bottom out, and in what order do you fill the table?

If you can write these three lines in English before touching code, coding the solution takes 5 minutes. If you can’t, don’t code yet.

Top-down (memoization) vs bottom-up (tabulation)¶

Both give the same big-O. Pick based on the problem, not on taste.

Aspect	Top-down (memo)	Bottom-up (tab)
Reads like	Recursion + cache	Loop filling an array
When it wins	Sparse state space, hard-to-derive fill order, tree/graph DP	Dense state space, need constant-space rolling window
Space	Recursion stack + memo table	Just the table (often shrinkable)
Debuggability	Easier — trace one recursive call	Harder — the whole table is filled
study default	Start here to reason, convert if asked	Convert to this when study partner asks for constant space

Rule of thumb: think top-down, code bottom-up when the grid is 1D or 2D and dense. For tree/graph DP, top-down is almost always the right choice.

Top-down template (Java)¶

Map<String, Integer> memo = new HashMap<>();

int solve(int i, int j) {
    if (i < 0 || j < 0) return 0;         // base case
    String key = i + "," + j;              // for 1D use Integer key directly
    Integer cached = memo.get(key);
    if (cached != null) return cached;

    int result = /* transition using solve(...) recursively */;
    memo.put(key, result);
    return result;
}

For dense integer states, prefer int[][] filled with Integer.MIN_VALUE (or a sentinel) — 5-10× faster than HashMap<String,Integer> on LeetCode.

Bottom-up template (Java)¶

int[][] dp = new int[n + 1][m + 1];
// base cases
for (int i = 0; i <= n; i++) dp[i][0] = 0;
for (int j = 0; j <= m; j++) dp[0][j] = 0;

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        dp[i][j] = /* transition using dp[i-1][j], dp[i][j-1], dp[i-1][j-1] */;
    }
}
return dp[n][m];

⚠️ What most people get wrong: they memoize on mutable state (a list, a set, an array) and pay O(n) to hash-key each call, wiping out the DP speedup. Memo keys must be small immutable tuples: primitives, String, or a canonical int encoding.

The 20 canonical problems¶

Solve every one of these by hand. Each cell tells you: state, transition, and the one insight that makes it click. Do them in order — later problems reuse the shapes of earlier ones.

1. Fibonacci (the “hello world” of DP)¶

State: dp[i] = i-th fib.
Transition: dp[i] = dp[i-1] + dp[i-2].
Insight: two variables suffice; no array needed.

long fib(int n) {
    if (n < 2) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
    return b;
}

2. Climbing stairs¶

State: dp[i] = ways to reach step i.
Transition: dp[i] = dp[i-1] + dp[i-2].
Insight: it’s literally fib. study partners love this because it teaches you to recognize fib in disguise.

3. House robber¶

State: dp[i] = max loot from houses 0..i.
Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Insight: the “take or skip” choice is the universal DP shape — you will see it 40 times.

4. Coin change (min coins)¶

State: dp[amt] = min coins to make amt.
Transition: dp[amt] = 1 + min(dp[amt - c]) for each coin c ≤ amt.
Base: dp[0] = 0, all others Integer.MAX_VALUE - 1 (avoid overflow when doing +1).
Insight: this is unbounded knapsack — each coin reusable. Contrast with 0/1 knapsack (below).

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);           // sentinel bigger than any real answer
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

5. Longest Increasing Subsequence (LIS)¶

State: dp[i] = length of LIS ending at index i.
Transition: dp[i] = 1 + max(dp[j]) for j<i, nums[j]<nums[i].
Naive: O(n²). Optimal: O(n log n) using a patience-sort tails array + Arrays.binarySearch.

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = Arrays.binarySearch(tails, 0, size, x);
        if (i < 0) i = -(i + 1);
        tails[i] = x;
        if (i == size) size++;
    }
    return size;
}

Insight: tails[k] = smallest possible tail of any increasing subsequence of length k+1. Powerful — you will reuse this shape.

6. Longest Common Subsequence (LCS)¶

State: dp[i][j] = LCS of a[0..i-1] and b[0..j-1].
Transition: if a[i-1]==b[j-1]: dp[i][j] = dp[i-1][j-1] + 1; else max(dp[i-1][j], dp[i][j-1]).
Insight: the 2D grid DP archetype. Master this and you get edit distance, min ASCII delete, shortest common supersequence for free.

7. Edit distance (Levenshtein)¶

State: dp[i][j] = min ops to convert a[0..i-1] → b[0..j-1].
Transition: if match: dp[i-1][j-1]; else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
Base: dp[i][0] = i, dp[0][j] = j.
Insight: three operations (insert/delete/replace) become three neighboring cells. This is Git-diff, DNA alignment, spell-check.

8. 0/1 Knapsack¶

State: dp[i][w] = max value using first i items, capacity w.
Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) if item fits.
Space trick: iterate w from W down to weight[i] and use a 1D array.
Insight: the “take or skip” pattern in 2D. Every subset-sum, partition-equal, target-sum problem is a knapsack.

9. Unique paths (m×n grid, right/down only)¶

State: dp[i][j] = ways to reach cell (i,j).
Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1].
Insight: the pure 2D combinatorial shape. Add obstacles → unique paths II. Add cost per cell → min path sum (#18).

10. Word break¶

State: dp[i] = can s[0..i-1] be segmented?
Transition: dp[i] = OR over j<i of (dp[j] && wordSet.contains(s[j..i-1])).
Insight: a 1D DP where each step “cuts” the string. Put words in a HashSet<String> for O(1) contains.

11. Palindrome partitioning (min cuts)¶

State: dp[i] = min cuts for s[0..i].
Trick: precompute isPal[l][r] in O(n²) first, then dp[i] = min(dp[j-1] + 1) for isPal[j][i].
Insight: the two-DP-in-sequence pattern. Doing them in one pass is a common bug — separate concerns.

12. Matrix chain multiplication¶

State: dp[i][j] = min scalar multiplications to compute A_i · … · A_j.
Transition: dp[i][j] = min over k of (dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]).
Insight: interval DP — you split on k inside [i,j]. Same shape as burst balloons (#17), stone game, MCM.

13. Rod cutting¶

State: dp[n] = max revenue from rod of length n.
Transition: dp[n] = max(price[i] + dp[n-i]) for 1 ≤ i ≤ n.
Insight: unbounded knapsack in different clothing. If they say “cut a thing into pieces to maximize value,” think rod cutting.

14. Egg drop (K eggs, N floors)¶

State: dp[k][n] = min worst-case trials with k eggs, n floors.
Transition: dp[k][n] = 1 + min over x of max(dp[k-1][x-1], dp[k][n-x]).
Optimization: binary search the inner x since one term rises and the other falls — O(K·N·log N).
Insight: min-max DP — you minimize the worst case. Classic Google/Facebook question.

15. Regex match (`.` and `*`)¶

State: dp[i][j] = does s[0..i-1] match p[0..j-1]?
Transition: if p[j-1] == '*': dp[i][j] = dp[i][j-2] || (matches(i,j-1) && dp[i-1][j]); else dp[i][j] = dp[i-1][j-1] && matches(i,j).
Insight: * means “zero of preceding” OR “one more of preceding.” Base case dp[0][j] for patterns like a*b*c* matching empty string.

16. Wildcard match (`?` and `*`)¶

State: same as regex.
Transition: simpler — * matches any sequence. dp[i][j] = dp[i-1][j] || dp[i][j-1] when p[j-1]=='*'.
Insight: wildcards are strictly easier than regex — no “preceding char” coupling.

17. Burst balloons¶

State: dp[i][j] = max coins bursting all balloons strictly between i and j.
Transition: dp[i][j] = max over k in (i,j) of (dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).
Insight: the reversal trick — instead of “which balloon to burst first?” ask “which balloon to burst last?” That’s what makes the neighbors nums[i] and nums[j] stay put.

18. Min path sum (grid)¶

State: dp[i][j] = min sum reaching (i,j).
Transition: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Space: roll to 1D (dp[j] only).
Insight: the value-carrying variant of unique paths. Master both together.

19. Decode ways¶

State: dp[i] = number of decodings of s[0..i-1].
Transition: two contributions — one digit (if s[i-1] != '0') and two digits (if 10 ≤ int(s[i-2..i-1]) ≤ 26).
Insight: the constrained-fib shape. Edge cases around '0' are what study partners grade you on.

20. Jump game (I and II)¶

Jump I (can reach end?): greedy, not DP — track maxReach. Included here because the trap is people write DP and get O(n²) when O(n) exists.
Jump II (min jumps): BFS-in-disguise — track current window [curEnd, farthest].
Insight: know when DP is overkill. If greedy works, use it. study partners pay attention to that call.

Recognizing DP in the wild (pattern signatures)¶

You have ~2 minutes in an study to decide “this is DP.” Use this table.

Signal in the prompt	Likely DP shape
“count the number of ways”	Combinatorial DP (unique paths, decode ways, climb stairs)
“max/min … subject to constraint”	Optimization DP (knapsack, house robber, min path)
“longest / shortest sub-sequence”	Sequence DP (LIS, LCS, edit distance)
“can you partition / can you reach”	Boolean DP (word break, partition equal, subset sum)
“you can do operation any number of times”	Unbounded knapsack (coin change, rod cutting)
“given a range/interval and split it”	Interval DP (MCM, burst balloons, palindrome partitioning)
“K eggs / K transactions / K rounds”	Add K as a state dimension

⚠️ What most people get wrong: they try to compress the state before proving the DP works. Get the correct O(state × transition) solution first, then optimize the state (roll 2D to 1D, use two variables instead of an array). Optimizing prematurely produces subtle off-by-ones you cannot debug.

Complexity summary¶

Problem	Time	Space (naive)	Space (optimized)
Fib, climb, house robber	O(n)	O(n)	O(1)
Coin change	O(n·amount)	O(amount)	O(amount)
LIS	O(n²) or O(n log n)	O(n)	O(n)
LCS, edit distance, unique paths	O(n·m)	O(n·m)	O(min(n,m))
0/1 knapsack	O(n·W)	O(n·W)	O(W)
Word break	O(n²) with set	O(n)	O(n)
Palindrome partition (min cuts)	O(n²)	O(n²)	O(n²)
MCM, burst balloons, palindrome interval	O(n³)	O(n²)	O(n²)
Egg drop	O(K·N·log N)	O(K·N)	O(K·N)
Regex/wildcard	O(n·m)	O(n·m)	O(n·m)
Decode ways	O(n)	O(n)	O(1)

Practice slate (do these in this order)¶

Solve top-down first, then convert the top 5 to bottom-up as a drill.

LeetCode 70 Climbing Stairs (Easy)
LeetCode 198 House Robber (Medium)
LeetCode 213 House Robber II — circular array
LeetCode 322 Coin Change (Medium)
LeetCode 300 Longest Increasing Subsequence — both O(n²) and O(n log n)
LeetCode 1143 Longest Common Subsequence (Medium)
LeetCode 72 Edit Distance (Medium/Hard)
LeetCode 416 Partition Equal Subset Sum (0/1 knapsack)
LeetCode 62 Unique Paths + 63 Unique Paths II
LeetCode 139 Word Break (Medium)
LeetCode 132 Palindrome Partitioning II (Hard)
LeetCode 887 Super Egg Drop (Hard)
LeetCode 10 Regular Expression Matching (Hard)
LeetCode 44 Wildcard Matching (Hard)
LeetCode 312 Burst Balloons (Hard)
LeetCode 64 Minimum Path Sum (Medium)
LeetCode 91 Decode Ways (Medium)
LeetCode 45 Jump Game II (Medium)
LeetCode 518 Coin Change II (unbounded, count ways)
LeetCode 887 Two Keys Keyboard / 651 Four Keys (interval-ish)

Target: 20 problems in 15 hours across two weeks. On problems 6-15, force yourself to write the state/transition/base in English first, in a code comment, before typing any Java.

Return to README.md · Next: 06_problem_solving_strategy.md