Part 9: Dynamic Programming — The DSA Handbook

9.0intermediate
Dynamic Programming: From Recursion to Memoization
When a recursion's call tree carries redundancy, an eight-character cache drops Fibonacci from O(phi^n) to O(n). The systematic move from naive recursion to memoized recursion to bottom-up tabulation.
20 min
9.1intermediate
DP: bottom-up tabulation
Convert memoized recursion to an iterative table fill: dependency DAG, topological order, loop, array. Plus the rolling-pair O(1) compression.
20 min
9.2intermediate
Dynamic programming on a 1D state
1D-state DP: when the answer at index i depends on a small fixed window of earlier indices. Climbing stairs, house robber, min cost climbing stairs, and the rolling-scalars space collapse.
15 min
9.3intermediate
Decode Ways and Word Break: string-prefix decision DP
Two string-prefix decision DPs whose recurrences look different but run on the same dp[i] = OR-over-valid-splits skeleton. LC 91 Decode Ways and LC 139 Word Break.
20 min
9.4intermediate
0/1 knapsack
0/1 knapsack: take-or-skip per item, the 1D table fill, why the inner loop sweeps right-to-left, and the family of subset-sum reformulations (LC 416, 494, 474, 879, 1049).
15 min
9.5intermediate
Unbounded knapsack: when items can be picked over and over
One inner-loop direction reversed from 0/1 knapsack unlocks the coin-change family. How 'minimum coins', 'count of ways', and 'minimum cost' all fit one recurrence.
20 min
9.6intermediate
Longest common subsequence
The O(n*m) 2D DP for longest common subsequence, parent-pointer recovery for the actual subsequence, and the edit-distance and shortest-common-supersequence variants that live on the same table.
30 min
9.7intermediate
Edit distance
Wagner-Fischer's three-way recurrence for the minimum number of insertions, deletions, and replacements that turn one string into another. The canonical 2D string DP.
15 min
9.8intermediate
Longest Increasing Subsequence: the quadratic DP
Per-index dp[i] = max-over-smaller-predecessors gives the O(n^2) LIS. Parent-pointer recovery and the variants (LIS count, LIS with k-tolerance) that stay quadratic.
15 min
9.9advanced
LIS: patience sort
From 9.8's O(n^2) DP to O(n log n): the patience-sort framing, the tails-array invariant, binary search by tail value, and the LC 354 sort-then-LIS reduction.
20 min
9.10intermediate
Palindrome DP
Filling a 2D table whose recurrence reads dp[i+1][j-1] forces a diagonal fill order. The longest-palindromic-substring and min-cuts family that lives on it.
20 min
9.11advanced
Interval DP: matrix chain and burst balloons
State is dp[l][r], and the recurrence picks the LAST operation in the range. Burst Balloons (LC 312) and Matrix Chain Multiplication (LC 1039) are the canonical specimens.
20 min
9.12intermediate
Grid DP: forward fills, backward survives
Top-down forward fills (Unique Paths, Min Path Sum) and bottom-up backward survives (Dungeon Game). The direction is picked by whether the constraint applies at start or finish.
25 min
9.13advanced
Tree DP: states that travel up the call stack
Post-order helpers that return more than one number to the parent — (rob, skip), (diameter, depth) — centered on LC 337 House Robber III and LC 124 Max Path Sum.
20 min
9.14advanced
Bitmask DP
A subset of a small ground set encoded as one integer, dp[mask] = ..., and the assignment / TSP / shortest-path-visiting-all family where this state is the only one that fits.
20 min