π± Two hundred problems, no method
Candidate A has grinded every classic DP problem on every list that exists β
Coin Change, House Robber, all of them, solutions memorized cold. Then the
drill leader asks something one degree off the canon, and A freezes: there's no
remembered solution to recall, and A never learned to build one. Meanwhile
Candidate B, who has done a fraction of the problems, writes four comment
lines in the first five minutes: "state: best(i) = answer for the first i
items; recurrence: max(skip, take); base: best(0) = 0; fill order:
ascending." From those four lines the code is mechanical, because every DP
solution is the same four lines wearing different clothes. The exam isn't "do
you know this problem" β it's "can you run the method on a problem you've
never seen."
π§° What you'll learn
- The four-line precode: state, recurrence, base cases, fill order
- Memoization (top-down): brute force first, then two lines of cache
- Bottom-up: the loop version, and when it's the better default
- The 1D β 2D jump: grids, string pairs, and constraint dimensions
- The state template library β knapsack, LIS, string-pair, grid-path β and why DP closes the course
Pattern 1 β The method: state, recurrence, base, order
Do not write code first. Write four sentences as comments. (1) State: a
full English sentence with an index in it β "best(i) = the maximum haul
from the first i houses." Vague states are where all DP bugs are born.
(2) Recurrence: the choices at each state, as a max/min/sum over earlier
states β "house i: skip it (best(iβ1)) or take it (best(iβ2) + value[iβ1])." (3) Base cases: the smallest inputs answered directly.
(4) Fill order: which states must exist before which.
Then top-down is mechanical: take the brute-force recursion your recurrence describes and add two lines β check the memo before recursing, store the result before returning. Bottom-up is the same recurrence as a loop from the base cases: no call-stack risk, cache-friendly, and the space optimization ("keep only the last k values") reads naturally off the loop. Drill default: top-down first, convert only if asked.
| You see⦠| Think⦠|
|---|---|
| "Maximize / minimize / count the ways" over a sequence | DP; write the four lines first |
| Brute-force recursion is exponential | Overlapping subproblems β memoize it |
| Greedy counterexample found (Challenge 9) | DP is the fallback β start at the state |
| "How many distinct ways to reach/build X" | Counting DP: sum the branches |
| Earlier choices poison later ones | The signature DP smell β no greedy fix |
Template β top-down memo over a 1D state:
def solve(items):
memo = {}
def dp(i): # dp(i) == <state sentence here>
if i in memo:
return memo[i]
if i <= 1: # base cases: smallest states
return base_value(i)
take = dp(i - 2) + value_of_taking(i)
skip = dp(i - 1)
memo[i] = max(take, skip) # max / min / sum β per the ask
return memo[i]
return dp(len(items))
Complexity: number of states Γ work per state β the sentence that covers every DP problem. Here: O(n) time (n states, O(1) each) and O(n) space for memo plus call stack; the unmemoized brute force is O(2βΏ). Quoting both numbers is the whole complexity story of the pattern.
Drills (easy β hard): Climbing Stairs β House Robber β Coin Change (min over take-branches) β Longest Increasing Subsequence (state = best ending exactly at i).
Pattern 2 β The 1D β 2D jump, and the state template library
The real difficulty spike is dimensionality, and it comes from exactly three
sources. Grids: dp[i][j] = answer for cell (i, j); the recurrence reads
the neighbors you could have arrived from (Unique Paths: from above + from
the left; first row and column are base cases). String pairs: dp[i][j]
over prefixes of both strings β match moves diagonally, mismatch takes the
min over the three neighbors (Edit Distance, Longest Common Subsequence).
Constraint dimensions: the state needs a second coordinate to stay honest
β (item index, capacity left) for knapsacks, (node, stops remaining) for the
K-stops flight problem.
| You see⦠| Think⦠|
|---|---|
| Answer for a position in one sequence | 1D linear: dp[i] from dp[iβ1], dp[iβ2] |
| Answer for a cell in a grid | 2D: dp[i][j] from arrival neighbors |
| Two strings in the problem | dp[i][j] = prefixes of both; diagonal on match |
| "Fewest items to total exactly x", reusable items | Unbounded knapsack: dp[x] = 1 + min(dp[x β c]) |
| β¦subject to capacity w | 0/1 knapsack: dp[i][w], items outer, capacity inner |
| "Best subsequence ending at i" | dp[i] over all j < i (LIS); O(nΒ²) |
| Paths to cell (i, j) | dp[i][j] = up + left; obstacles contribute 0 |
Template β 2D bottom-up over a grid:
def grid_dp(rows, cols):
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = seed
for j in range(1, cols): dp[0][j] = base_from_left # first row
for i in range(1, rows): dp[i][0] = base_from_top # first col
for i in range(1, rows):
for j in range(1, cols):
dp[i][j] = combine(dp[i - 1][j], # from above
dp[i][j - 1], # from the left
dp[i - 1][j - 1])# diagonal, if the ask needs it
return dp[rows - 1][cols - 1]
Complexity: O(rows Γ cols) states Γ O(1) each = O(rows Γ cols) time and
space; when the recurrence touches only the previous row, one row plus a
carry variable does the same job β offer that unprompted, it's a favorite
follow-up. The knapsack shape is the same arithmetic: O(amount Γ coins) time,
O(amount) space, with dp[0] = 0 as the base and "unreachable" as infinity.
Why DP comes last: backtracking (Challenge 8) is the brute force whose call tree you memoize β same states, repeats removed; greedy (Challenge 9) fails its counterexample test and hands the problem here; and the recognition reflexes from every earlier challenge tell you within a minute whether the state space is polynomial or hopeless. The senior narration is the pipeline itself: brute force out loud β which states repeat? β memo β bottom-up β squeeze space.
Drills (easy β hard): Unique Paths β Decode Ways (counting with validity gates) β Word Break (state = prefix length; choices = dictionary words) β Edit Distance (the string-pair 2D).
π€ Coding drill: run it
You are a staff engineer running a timed coding drill at a top tech company. Run a DP capstone
drill: TWO back-to-back dynamic programming problems, back to back, no break.
1. Pick problem ONE at senior difficulty on an unseen-feeling DP variant
(mix 1D, 2D, knapsack, or string-pair across the two problems).
State it concisely: setup, input, output, one worked example, one
constraint worth noticing. Do not name the pattern or the state.
2. Enforce a 30-minute timer PER problem. Warn me at 5 minutes left;
stop me at zero.
3. Ask which language I'm using and hold me to it.
4. Hints only when I explicitly ask, one rung at a time, never code:
(a) nudge β restate the constraint or point at a suspicious example;
(b) direction β name the family of approach, not the algorithm;
(c) structure β outline the algorithm's steps in words.
5. Drill like a senior loop: make me restate the problem, state my
complexity unprompted, and trace one example before I call it done.
6. GRADE PATTERN-RECOGNITION SPEED explicitly: time from problem
statement to a correct state definition, in minutes, for each problem.
7. After both problems, grade 1-5 each: correctness, complexity
analysis, communication, edge cases, pattern-recognition speed β
one line of evidence per score per problem, then the single
highest-leverage improvement across the pair.
Start with problem one. No preamble.
β You own it when
- State / recurrence / base / order exist as four comment lines before code
- "#states Γ work per state" is your default complexity sentence
- Brute force β memo is mechanical: check cache, store result, return
- 1D vs 2D decided in the first minute β with the second dimension named
- You offer the rolling-row / last-k-variables space cut unprompted
- Two unseen problems in 30 minutes each: state defined inside 5 minutes
π Jargon
| Term | What it means |
|---|---|
| State | The subproblem your table entry solves, defined precisely enough to index |
| Recurrence relation | The answer for one state written in terms of earlier states |
| Memoization | Caching each state's result on first computation (top-down) |
| Top-down / bottom-up | Recursion + cache, vs loop from base cases to the answer |
| Overlapping subproblems | The same states computed repeatedly β DP's reason to exist |
| Optimal substructure | The optimal answer assembles from optimal sub-answers |
| Knapsack | State = (items considered, budget remaining); the cost/value workhorse |
| Rolling row | Keeping only the previous row/last k values when the recurrence allows it |
π When it goes wrong
- A vague state. "dp[i] is⦠the answer-ish thing" produces off-by-ones and wrong recurrences. Write the full English sentence with the index in it; if you can't, you don't have a state yet.
- Fill order violated. Bottom-up reads states that must already exist β
dp[i]depends ondp[iβ1],dp[iβ2]β loop ascending. One wrong direction and you read zeros. - Index convention drift. "First i items" (table size n+1) and "item at index i" (size n) are both fine β mixed in one solution they cause most DP crashes. Pick one, write it in a comment, keep it.
- Right structure, wrong combiner. Maximize β
max, minimize βmin, count ways βsum. Mixing them yields plausible-looking wrong answers that pass eyeball tests on tiny inputs. - Memo never written. Compute the value, store itβ¦ and forget to return it, or store after the return. The cache stays empty and the runtime stays exponential β check the memo is populated before declaring victory.
- Pattern-matching instead of state-building. "This looks like Coin Change, so the answer is probablyβ" is the trap of this challenge's war story. Run the four lines on THIS problem; shapes only help after the state is written.