Dynamic Programming
The skill that separates medium solvers from hard solvers
DP is where most people get stuck, and it’s the core of ~35% of hard problems. The secret: DP is just recursion + memoization. If you completed Stage 2’s backtracking problems, you already think recursively — now you’re just caching results. Start by writing the brute-force recursion, THEN add memoization, THEN convert to bottom-up if needed.
For each problem, write the solution THREE ways: (1) recursive brute force, (2) top-down with memo, (3) bottom-up table. This builds real understanding, not pattern matching.
📏1D DP
The simplest DP structure: dp[i] depends on previous dp values. Master this before anything else.
Fibonacci in disguise. dp[i] = dp[i-1] + dp[i-2]. Start here.
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The ‘take or skip’ template.
O(n²) DP first, then learn the O(n log n) patience sorting approach.
dp[i] = can we segment s[0..i]? Try all possible last words.
Track both max AND min at each position (negatives flip signs).
Like climbing stairs but with constraints on which steps are valid.
🗺️2D DP
Two-dimensional state: dp[i][j] might mean ‘best answer using first i items with capacity j’ (knapsack) or ‘answer for substring s[i..j]’ (interval). This covers most medium DP and opens the door to hards.
dp[i][j] = dp[i-1][j] + dp[i][j-1]. Grid DP starting point.
The classic 2D string DP. Understand match vs. skip transitions.
0/1 Knapsack. dp[j] = can we make sum j? Space-optimize to 1D.
Count knapsack variant. Or transform to subset sum with math.
dp[i][j] = min edits for s1[0..i] → s2[0..j]. Three transitions: insert, delete, replace.
2D DP on string vs pattern. The ‘*’ case has two transitions. Think carefully.
🌲DP on Trees & Intervals
Combines your tree recursion skills with DP. This is the bridge to hard problems like tree DP with rerooting, interval scheduling, and later, segment tree optimized DP.
House Robber on a tree. Return (rob_this, skip_this) pair from each subtree.
Catalan numbers via DP. dp[n] = Σ dp[i-1] * dp[n-i].
Interval DP or greedy with monotonic stack. Try both!
Interval DP. The trick: think about which balloon you burst LAST, not first.
Interval DP. Sort cuts, then dp[i][j] = min cost to process segment.