Stage 1 · Code
Dynamic Programming & Greedy
DP Drills
From 1D recurrence to 2D tables, string alignment, and state machines — drill the DP patterns that appear most in interviews.
12 min readLeetCode Patterns for InterviewsCode
The DP Mindset
Dynamic programming is recursion + memoisation turned inside out. The hard part is never the code — it's identifying the state variables. Ask: what decisions lead from one subproblem to the next? The answer defines your DP table dimensions.
Complexity growth across DP patterns
1D DP (Fibonacci)
O(n)
Linear scan, constant space possible
2D DP (LCS)
O(n·m)
Matrix of prefixes, quadratic in worst case
Naive recursion
O(2ⁿ)
Before memoisation — exponential blowup
Always start with brute force
Write a recursive solution first. Then add memoisation. Then (optionally) convert to bottom-up tabulation. This progression works for every DP problem — never try to write the bottom-up table directly on the first attempt.
DP Patterns
| Pattern | State (i = index) | Recurrence |
|---|---|---|
| 1D DP (Fibonacci-style) | dp[i] = best up to i | dp[i] = f(dp[i-1], dp[i-2]) |
| House Robber (take/skip) | dp[i] = max gain up to i | dp[i] = max(dp[i-1], nums[i] + dp[i-2]) |
| 0/1 Knapsack | dp[i][w] = max value with first i items, weight ≤ w | dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]]) |
| String DP (LCS, Edit Dist) | dp[i][j] = best up to s1[:i], s2[:j] | Match → 1+dp[i-1][j-1]; else max/min of adjacent |
| State Machine (Buy/Sell Stock) | dp[i][k][holding] | dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+price) |
| Unbounded (Coin Change) | dp[a] = min coins to make amount a | dp[a] = min(dp[a], 1 + dp[a - coin]) |
Problems
#70Climbing StairsEasy1D DP — Fibonacci · O(n) time · O(1) with two variables space#322Coin ChangeMediumUnbounded knapsack · O(amount × len(coins)) time · O(amount) space#300Longest Increasing SubsequenceMedium1D DP · O(n²) time · O(n) space#72Edit DistanceMedium2D string DP · O(m × n) time · O(m × n) space#198House RobberMedium1D DP take/skip · O(n) time · O(1) space#309Best Time to Buy and Sell Stock with CooldownMediumState machine DP · O(n) time · O(1) space
Key Points
- Start recursive, add memo, then bottom-up — the only reliable DP workflow.
- 1D DP is usually a scan with 2–3 previous values — space optimisation to O(1) is often possible.
- 2D DP tables for strings — LCS, edit distance, longest palindrome all build a matrix of prefixes.
- State machines for buy/sell stock — holding/not-holding/cooldown are finite states, not indices.
- Knapsack variant: 0/1 vs unbounded — 0/1 iterates items outer loop; unbounded iterates amount outer loop.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.