Dynamic Programming

The most-feared topic, made mechanical. DP is just recursion whose subproblems overlap, so you compute each once and reuse it — and every DP is the same four decisions (state, transition, base, order). Learn to run that recipe and the "families" are just different shapes of state.

Series map: 00 playbook · 01 two pointers & sliding window · 02 binary search, stacks & intervals · 03 trees & graphs · 04 recursion & backtracking · 05 dynamic programming (this file) · 06 staff+ practical & OOD. Companion (non-series): data-structures-java-kotlin-study-guide.md — reach there for why a HashMap / ArrayDeque / array behaves as it does (buckets, boxing, cache locality). This guide uses those as tools and spends its words on the algorithm.

The mental model#

A dynamic program is a recursion whose subproblems overlap, so instead of recomputing them you compute each exactly once and reuse the result. Every DP is exactly four things: (1) a STATE that fully captures a subproblem, (2) a TRANSITION — the recurrence relating a state to smaller states, (3) BASE cases — the smallest states you answer directly, and (4) an ORDER of evaluation so every state's dependencies are ready before it. If you can write the brute-force recursion, the DP is already 90% done: you either "cache it" (top-down memoization) or "fill a table in dependency order" (bottom-up tabulation).

Two facts drive everything:

• DP ⊂ recursion. The only thing that turns exponential brute force into polynomial DP is overlap: the same subproblem is reached by many paths. Naive Fibonacci recomputes fib(3) a huge number of times; memoizing collapses O(2ⁿ) to O(n). If subproblems don't overlap (e.g. generating all permutations, all distinct), memo buys nothing — that's backtracking (guide 04), not DP. The tell for DP is "count the ways" or "optimize (min/max)" over choices with reused subproblems, not "list all."
• Top-down and bottom-up are the same recurrence, two directions. Top-down (memoized recursion) is closest to the brute force and easiest to get right — write it first. Bottom-up (a filled array) removes recursion overhead, makes the evaluation order explicit, and is what unlocks space optimization (rolling arrays). In a room: derive top-down, then offer bottom-up + O(1) space as the flourish.

The universal method — run this on any DP prompt:

Everything below is this table with different state shapes.

1. From recursion to DP, concretely — the four-step conversion#

Recognition cue. You can describe the answer as "the best/number of ways for input n, in terms of the same question on smaller inputs," and the recursion tree revisits subproblems.

Take the plainest example. Climbing stairs: you take 1 or 2 steps at a time; how many ways to reach step n? The recurrence is ways(n) = ways(n-1) + ways(n-2) (last move was a 1-step or a 2-step), base ways(0)=ways(1)=1. That is literally Fibonacci.

Stage 0 — brute-force recursion (exponential, but correct). The call tree for ways(5) computes ways(3) twice, ways(2) three times… O(φⁿ) calls. This is the version you should be able to write in your sleep; the DP is a transformation of it.

Stage 1 — top-down memo (add a cache; O(n)). One line of thought: "before I recompute a state, check whether I already have it." The memo turns the tree into a DAG — each state solved once.

Stage 2 — bottom-up tabulation (fill the array in order; still O(n)). The dependency order is obvious (i needs i-1, i-2), so iterate ascending. No recursion, no stack risk.

Stage 3 — space optimization (only the last two states matter; O(1)). The transition reads a fixed window (i-1, i-2), so keep two scalars, not an array. This is the "…and I can reduce it to O(1) space" line that reads as senior.

This is the whole game. Every DP below is: write the recurrence → memoize → tabulate → (maybe) shrink space. Time is #states × work-per-state; space is #states, reducible when the transition only reaches a bounded window of prior states.

Traps in §1:

• Sentinel collision. Using 0 as "not computed" fails when 0 is a legal answer. Use -1 for non-negative results, or a separate boolean[] seen.
• Overlap check. If the recursion tree has no repeats, memoization does nothing — you're in backtracking territory, not DP. Confirm overlap before reaching for a table.
• Depth on top-down. Deep recursion (n ≈ 10⁵) can StackOverflowError; bottom-up sidesteps it. Say this out loud.

2. How to FIND the state — the actually-hard part#

Given a brute force, the state is the set of arguments the recursive function needs. Ask: "what varies across subproblems, and what's the minimum I must remember to answer one?" Every parameter that changes the answer must be in the state; anything derivable or fixed must not (bloats the table and breaks caching only if you forget something that matters — see the last trap in this guide).

Heuristic: read the state off the constraints (the trick from guide 00). The input size tells you the target complexity, which tells you the state dimensionality:

Backend aside (one, then back to algorithms): your accumulative OCPI charging-session aggregate — folding an ordered event stream into a single session object — is a degenerate 1-D DP: the "state" is the running accumulator, the "transition" applies the next event, and each prefix is computed once. Most production code is this fold with no choice at each step; interview DP just adds a min/max/count over choices and asks for the optimum. You already think in states and transitions.

The single most common failure is a state that doesn't capture enough — two genuinely different subproblems collide on one key and the answer is wrong on some inputs. The fix is always: find two inputs that should give different answers but map to the same state, and add the discriminating dimension.

3. Linear / 1-D DP — one index#

Recognition cue. A single sequence; the answer at position i depends on a bounded window of earlier positions. "In how many ways," "min/max cost along a line," "can you reach the end," climb/rob/decode.

House Robber I & II (non-adjacent max; II is circular)#

English recurrence: "best up to house i = max of (skip i: best up to i-1) and (rob i: nums[i] + best up to i-2)." Two rolling scalars.

House Robber II — houses in a circle, so first and last are adjacent. Rob [0, n-2] or [1, n-1], take the max; handle n == 1 separately. Reuse the linear helper:

Kadane — maximum subarray; and maximum product subarray#

Kadane's insight: "the best subarray ending at i either extends the best ending at i-1, or restarts at i." O(n) / O(1).

Maximum product subarray adds a twist: a negative flips largest↔smallest, so you must track both a running max and a running min. On a negative element, swap them before updating.

Min cost climbing stairs · Decode ways · Word break (Kotlin; Java is the mechanical translation)#

Min cost climbing stairs — pay cost[i] to leave step i; reach the top from step 0 or 1. dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]), answer dp[n].

Decode ways — digit string → letters (A=1…Z=26). "ways to decode the first i chars = (take one digit if non-zero) + (take two digits if in 10..26)." Guard the leading '0' and any invalid two-digit.

Word break — can s be cut into dictionary words? dp[i] = OR over j<i of (dp[j] && s[j..i) ∈ dict). Put the dictionary in a HashSet for O(1) membership.

Jump Game I & II — where greedy beats DP#

Jump Game I ("can you reach the end?") has a clean O(n²) DP, but the greedy reachability scan is O(n)/O(1) and strictly better — track the farthest index reachable so far; if you ever stand beyond it, you're stuck.

Jump Game II ("fewest jumps to the end") is greedy-BFS by layers: within the current jump's reach, precompute the farthest you could next reach; when you hit the current frontier, you must jump, so bump the count and extend the frontier.

Complexity (this section): all O(n) time; O(1) space via rolling scalars, except word break (O(n²·L) from substrings). Trap: Kadane/product/robber seed from nums[0] — guard the empty array if constraints allow it. Trap: greedy is only correct for these specific "reachability / min jumps" shapes; the moment jumps have weights/costs, fall back to real DP.

4. Grid / 2-D DP — two indices over a matrix#

Recognition cue. A 2-D grid where each cell's answer depends on neighbors already computed (usually up and left). "Paths from corner to corner," "min/max path sum," "largest square/region ending here."

Unique Paths I & II#

"Paths to (i,j) = paths from above + paths from the left." Roll the 2-D table into one row (dp[j] after processing row i holds the current row; dp[j-1] is already this row's left neighbor, dp[j] still the row above).

Unique Paths II adds obstacles — an obstacle cell contributes 0 paths. Same roll, zero out blocked cells:

Minimum Path Sum · Triangle · Maximal Square (Kotlin; Java mechanical)#

Minimum path sum — same roll, min instead of +:

Triangle min path — cleanest bottom-up: start from the last row and fold upward, dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).

Maximal square — dp[i][j] = side of the largest all-1 square with bottom-right corner at (i,j); if the cell is 1, dp[i][j] = min(up, left, diag) + 1. Rolled to one row, you must stash the diagonal (dp[i-1][j-1]) before overwriting it.

Dungeon Game — why you MUST go bottom-up from the destination#

Recognition cue for "reverse" DP: the constraint (health must stay ≥ 1 at every step) depends on the future, not the past. If you sweep top-left→bottom-right tracking accumulated health, you can't know how much you'll need later, so a forward greedy/DP is wrong. Define dp[i][j] = minimum HP needed entering (i,j) to survive to the princess, and sweep bottom-right→top-left: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) − dungeon[i][j]).

The Int.MAX_VALUE seeds are safe here because for every real cell at least one neighbor toward the exit is finite, so min(...) never picks two sentinels. Complexity: grid DP is O(m·n) time; O(n) space with a rolled row (Dungeon keeps two rows / a full table for clarity). Trap: rolling a grid to one row only works when the transition reaches left and up (and diagonal, if you stash it) — never a cell you've already overwritten this row without saving it.

5. The Knapsack family — capacity as state, and the loop-order that trips everyone#

Recognition cue. You pick a subset of items under a capacity/budget/target, optimizing value or counting ways. "Can I hit this sum," "fewest coins," "how many ways to make change." State is dp[capacity] after considering some prefix of items.

0/1 knapsack — each item at most once → iterate capacity DESCENDING#

dp[c] = best value using capacity c. For each item, dp[c] = max(dp[c], dp[c-w] + v). In the rolled 1-D array you must iterate capacity downward so dp[c-w] still refers to the previous item's row (item not yet taken at this capacity) — that's what enforces "at most once."

Partition Equal Subset Sum is 0/1 subset-sum: total must be even; can we hit sum/2? Boolean knapsack.

Target Sum (assign +/− to reach S) reduces to counting subsets: let P be the positive set; P − (sum−P) = S ⇒ P = (sum+S)/2. Count subsets summing to P (a counting 0/1 knapsack — note +=, not ||).

Last Stone Weight II — smash stones; minimize the final remainder. That is sum − 2·(largest subset sum ≤ sum/2) — a boolean 0/1 knapsack, then scan down for the best reachable sum.

Unbounded knapsack — items reusable → iterate capacity ASCENDING#

Now each item may be used many times, so dp[c-w] should already include the current item at this pass — iterate capacity upward.

Coin Change (fewest coins) — the classic. Use amount+1 as the "impossible" sentinel, not Integer.MAX_VALUE: adding +1 to MAX_VALUE overflows to a negative and corrupts the min.

Rod cutting is the maximizing twin (cut lengths reusable):

The Staff-level subtlety: combinations vs permutations = which loop is OUTER#

This is the knapsack question senior interviewers love, because the two look identical but the loop nesting flips the meaning.

Coin Change 2 — count combinations (order irrelevant): coins OUTER, amount INNER. Fixing coins on the outside means once you finish a coin you never place it "before" an earlier coin again, so {1,2} and {2,1} are the same single combination.

Combination Sum IV — count permutations (order matters): amount OUTER, coins INNER. For each target you try every coin as the last step, so 1+2 and 2+1 are counted separately.

Why the order changes the meaning — say this in the room: the outer loop is the dimension you commit to first. Put items outside and you enumerate multisets (a coin can only follow coins already fixed → each unordered combination once). Put target outside and at each amount you branch over all items as the final piece → you count ordered sequences. Same recurrence dp[c] += dp[c-x]; different nesting, different counting semantics. The two capacity directions (descending = use-once, ascending = reuse) and the two nestings (item-outer = combinations, target-outer = permutations) are four independent knobs — know all four.

Complexity: O(#items · capacity) time, O(capacity) space for every variant above. Trap: counting DPs (+=) can overflow int even when the final answer fits — Combination Sum IV and Target Sum are the usual offenders; switch the accumulator to long if constraints are loose.

6. Subsequence & string DP — one or two sequences#

Recognition cue. One or two strings/arrays; you compare characters and either match-and-advance-both or skip one. Almost always dp[i][j] over the two prefixes; index discipline (dp[i] = first i chars, so the char is s[i-1]) is where people bleed points.

Longest Increasing Subsequence — the O(n²) DP and the O(n log n) upgrade#

O(n²): dp[i] = length of the LIS ending at i = 1 + max(dp[j]) over j<i with nums[j] < nums[i].

O(n log n) — patience sorting / tails: keep tails, where tails[k] is the smallest possible tail of any increasing subsequence of length k+1. For each x, binary-search the first tail ≥ x and overwrite it (append if none). The length of tails is the LIS length. (tails itself is not a valid subsequence — don't claim it is.)

For non-strictly increasing (allow equals), search the first tail strictly greater than x (upper_bound) instead. That one comparison flip is a favorite follow-up.

Longest Common Subsequence — the mother of two-string DP#

"If the last chars match, 1 + LCS of both prefixes; else the best of dropping one char from either string."

Edit Distance (Levenshtein) — insert / delete / replace#

Non-match cost is 1 + min(replace = diag, delete = up, insert = left); the base row/column are 0..n (turning a string into empty costs one delete per char), which people forget to seed.

The rest of the string-DP zoo (Kotlin; each is a small variation)#

Longest Palindromic Subsequence = interval DP on one string (or LCS(s, reverse(s))): match the two ends → +2, else drop an end.

Longest Palindromic Substring (contiguous) — don't reach for a table; expand around each of the 2n−1 centers is O(n²) time, O(1) space and easier to get right.

Distinct Subsequences — count subsequences of s equal to t. Match → use it (dp[i-1][j-1]) plus skip it (dp[i-1][j]); non-match → only skip. Base dp[i][0] = 1 (one way to form empty t).

Interleaving String — is s3 a merge of s1 and s2 keeping order? dp[i][j] true if the next char of s3 can come from s1 (and dp[i-1][j]) or s2 (and dp[i][j-1]). Length check first.

Regular-Expression Matching (. = any char, * = zero-or-more of the preceding). The * branch: zero occurrences (dp[i][j-2]) OR one-more if the preceding pattern char matches s[i-1] (dp[i-1][j]).

Wildcard Matching (? = one char, * = any sequence). Simpler *: match empty (dp[i][j-1]) or consume one char (dp[i-1][j]).

Longest Common Substring (contiguous, ≠ subsequence): dp[i][j] = length of the common suffix ending at a[i-1], b[j-1]; reset to 0 on mismatch; track the max.

Complexity (this section): two-string DPs are O(m·n) time and O(m·n) space, reducible to O(min(m,n)) with two rolled rows; LIS is O(n log n) / O(n); palindromic-substring by expansion is O(n²) / O(1). Traps: off-by-one (dp[i] ↔ s[i-1]); forgetting the base row/column in edit distance / distinct subsequences; using a table for palindromic substring when expansion is simpler; and conflating substring (contiguous, resets on mismatch) with subsequence (may skip).

7. Interval DP — dp[l][r] over a range, split at k#

Recognition cue. The answer for a range [l, r] is built by choosing a split point / last operation k inside it and combining two sub-ranges: "burst/remove the last element," "best way to parenthesize," "min cuts." The order that makes dependencies ready is by increasing interval length (short ranges before the long ranges that contain them).

The template:

Burst Balloons — the "last to burst" reframe#

The trick that makes it a clean interval DP: don't think about the first balloon to burst (its neighbors keep changing) — think about the last balloon k to burst in the open interval (l, r). When k bursts last, its neighbors are exactly the boundaries l and r, so coins = a[l]*a[k]*a[r] + dp[l][k] + dp[k][r]. Pad the array with virtual 1s at both ends.

The Matrix-Chain-Multiplication shape is identical: dp[l][r] = min over k of dp[l][k] + dp[k+1][r] + cost(l,k,r) — same "iterate by length, split at k" skeleton, minimizing multiplication cost instead of maximizing coins.

Palindrome Partitioning II (min cuts) · Predict the Winner (Kotlin)#

Min cuts to split s into palindromes: precompute an isPal[i][j] table (itself interval DP), then cuts[i] = min over j≤i where s[j..i] is a palindrome of cuts[j-1] + 1.

Predict the Winner / Stone Game — two players take from either end optimally. Let dp[i][j] = the best score difference (me − opponent) achievable on nums[i..j]; taking an end gives value − dp[remaining] (the opponent then plays optimally on the rest). First player wins iff dp[0][n-1] ≥ 0.

Complexity: interval DP is O(n³) time (n² states × O(n) split), O(n²) space — which is why the constraint hint says n ≤ ~400. Trap: looping by l/r directly instead of by length evaluates dp[l][r] before its shorter sub-intervals exist. Trap (burst balloons): reasoning about the first balloon instead of the last makes the neighbors non-local and the recurrence wrong.

8. Bitmask DP — a subset as the state (n ≤ ~20)#

Recognition cue. Small n (≤ ~20), and the natural state is "which items have I used/visited?" — a set. Encode the set as the bits of an Int (mask); 2ⁿ states. Often paired with "…and where did I end?" (last).

The two primitives: mask and (1 shl i) != 0 tests membership; mask or (1 shl i) adds item i.

The Assignment Problem — cleanest bitmask template#

Assign n workers to n tasks minimizing total cost. dp[mask] = min cost to assign the first popcount(mask) workers to exactly the tasks in mask. The next worker is popcount(mask); try giving them each still-free task.

Travelling Salesman (Held–Karp) — mask + last city#

dp[mask][last] = min cost of a path that started at city 0, visited exactly the set mask, and currently sits at last. Extend to an unvisited next; finally close the tour back to 0. O(2ⁿ·n²).

The same mask-as-visited-set idea powers team/group partition ("split people into groups minimizing conflict" — iterate over submasks of the remaining set) and the shortest-superstring sketch (dp[mask][last] = shortest string covering the words in mask ending with word last, transition adds a word by its overlap). Complexity: O(2ⁿ · n) (assignment) to O(2ⁿ · n²) (TSP); space O(2ⁿ)–O(2ⁿ·n). Traps: 1 shl n overflows Int past n = 31 (and you'd never allocate 2³¹ anyway — this is strictly small-n); guard dp[mask] == INF before transitioning so unreachable states don't propagate garbage; and use INF = MAX/2 so INF + cost can't overflow.

9. Tree DP — one post-order pass, answer folded up#

Recognition cue. The structure is a tree and each node's answer depends on its children's answers. This is DP where the "order" is a post-order traversal (children before parent) and the "table" is the recursion's return value(s). Cross-reference guide 03 for the traversal mechanics; here the point is what you return.

House Robber III — rob a binary tree, no two adjacent nodes. Return a pair (robThis, skipThis) so the parent can choose without re-descending. rob = val + skipLeft + skipRight; skip = max(left) + max(right).

Binary Tree Maximum Path Sum — the classic "return one thing up, record another." Each node returns the best downward extension (val + max(leftGain, rightGain, 0)) but records into a global the best path that bends at it (val + leftGain + rightGain). Clamp negative child gains to 0 ("don't take that branch").

Tree Diameter is the same trick with lengths: return 1 + max(childDepths), record leftDepth + rightDepth (edges through the node) into a global. Complexity: all O(n) time, O(h) stack. Trap: trying to return the bending value — you can only return a straight extension, because the parent can attach to at most one of your branches.

10. Space optimization and reconstruction#

Rolling arrays. If the transition only reaches a bounded window of prior states, you don't need the whole table. 1-D linear DPs collapse to a few scalars (§1, §3). A grid or two-string DP where row i only reads row i-1 collapses to one or two rows (§4, §5); when it also reads the diagonal, stash that one value before overwriting (Maximal Square, §4). Knapsack collapses dp[i][c] to dp[c] — provided you get the loop direction right (§5). The recipe: space = size of the largest "frontier" the transition ever needs at once.

Reconstruction — recovering the actual solution, not just its value. Two techniques:

(a) Store a choice/parent pointer as you fill the table, then walk it back. Coin Change, recovering which coins:

(b) Backtrack over the filled table by re-deriving each choice from neighbors — no extra storage, but needs the full table (rules out the rolled version). LCS, recovering the subsequence itself:

The tradeoff to state out loud: reconstruction via parent pointers costs O(states) extra memory but works with a rolled table if you keep the pointers; table-backtrack is zero extra memory but forces you to keep the full O(states) table (so you can't also space-optimize). Interviewers frequently ask "now give me the actual items/string," and this is the answer.

11. How to COMMUNICATE a DP in a room#

The order you present a DP matters as much as the code — per the rubric research (guide 00), seniors are scored on judgment and driving the session, not raw speed.

1. Say the recurrence in ENGLISH first. "The best for i is the better of taking item i — its value plus the best for i−2 — or skipping it and keeping the best for i−1." If you can say it, you can code it; if you can't, more coding won't help.
2. Name the family and the state, with complexity, before typing. "This is 0/1 knapsack; state is dp[capacity], O(n·W) time, O(W) space." That one sentence pattern-matches you to a senior.
3. Write top-down memo first. It's the smallest edit from the brute force you already described, so it's the easiest to get right under pressure and the hardest to bungle the base cases on.
4. Then offer the upgrades as a flourish. "I can convert this to bottom-up to drop the recursion, and since the transition only looks back two states, roll it to O(1) space." Converting on request shows you understand why it works, not just a snippet.
5. Pre-empt the classic bug by naming it. "Rolled 0/1 knapsack iterates capacity descending so each item is used once — ascending would silently make it unbounded." Calling the trap before the interviewer does is the strongest possible signal.
6. Flag version/JVM facts. Kotlin IntArray(n) { init } vs Java new int[n] + Arrays.fill; Kotlin's Int.MAX_VALUE / 2 (or a domain sentinel like amount + 1) to dodge overflow; Integer.bitCount for masks. Mention top-down recursion depth on large n and the bottom-up fallback — that's production-readiness thinking, which 2026 infra rubrics (Snowflake-style) reward, and DP + graphs are exactly Snowflake's reputed emphasis.

Problems & how to solve them#

Problem: the DP is right on the samples but wrong on some inputs. Root cause: the state doesn't capture enough — two subproblems that should differ collide on one key (you forgot a dimension: the last choice, remaining budget, a parity/flag, or which end you took from). Fix: find two inputs that should yield different answers but hit the same state, and add the discriminating parameter. The state must make the subproblem's answer a pure function of the key alone.

Problem: rolled knapsack over- or under-counts (or reuses items it shouldn't). Root cause: wrong loop direction/nesting. 0/1 needs capacity descending (each item once); unbounded needs ascending (reuse). Counting combinations needs items outer; permutations needs target outer. Fix: decide two things explicitly — "can an item repeat?" (direction) and "does order matter?" (nesting) — and set the four knobs accordingly. Verify on coins=[1,2], amount=3: combinations → 2, permutations → 3.

Problem: answers are off by a constant, or the first row/column is wrong. Root cause: base-case / initialization error — dp[0] given the wrong meaning (empty subproblem vs first element), or the base row/column of a 2-D table left unseeded. Fix: define dp[0]/the base explicitly as the answer to the empty subproblem (edit distance: dp[i][0]=i; subset-count: dp[0]=1; reachability: dp[0]=true) and seed it before the loops.

Problem: coinChange/min-DP returns a huge negative or garbage. Root cause: using Integer.MAX_VALUE as "impossible," then computing dp[c-coin] + 1, which overflows to Integer.MIN_VALUE and wins the min. Fix: pick a sentinel that can't overflow under the transition — amount + 1 for min-coins, Int.MAX_VALUE / 2 for path/TSP costs — and check dp[target] > bound for "unreachable." Never +1 a MAX_VALUE.

Problem: string DP throws IndexOutOfBounds or mismatches by one. Root cause: mixing 1-based table indices with 0-based string indices — reading s[i] when the cell dp[i] represents the first i chars (whose last char is s[i-1]). Fix: commit to the convention "dp[i][j] = first i of a, first j of b; the chars are a[i-1], b[j-1]." Size the table (m+1)×(n+1) and let i,j run 1..m, 1..n.

Problem: top-down memo returns stale/wrong values (works recursively, breaks when cached). Root cause: memoizing on an incomplete key — the function's result depends on a parameter you didn't include in the cache key, so two different states share one cached answer. Fix: the memo key must equal the entire state. If a variable changes the return value, it belongs in the key (and thus in the table's dimensions). This is the state-capture bug wearing a caching hat.

Problem: top-down is correct but TLEs / StackOverflowError. Root cause: the memo isn't actually shared (re-allocated per call), or the recursion is O(n) deep on n ≈ 10⁵, or the key is a boxed HashMap where an array would do. Fix: allocate the memo once outside the recursion; convert to bottom-up to remove depth; prefer primitive int[]/int[][] over HashMap<StateKey, …> when the state is small integers (see the companion guide on boxing/cache costs).

Interview framing / how to sound senior#

• Derive the state from the brute force, don't guess it. "Brute force branches on take/skip at each index and recomputes prefixes, so the state is just the index — 1-D DP." Working forward from the recursion is the reproducible method; pattern-matching to a memorized table is what fails on the twist.
• Read the state off the constraints. n ≤ 20 → bitmask; n ≤ 400 → interval O(n³); n,m ≤ 10³ → 2-D O(nm); n ≤ 10⁵ → 1-D O(n)/O(n log n). Announcing this before coding is a Staff-level tell.
• Name the family and both complexities up front. "Unbounded knapsack, O(n·amount) time, O(amount) space." Ties in the hiring committee break toward candidates who are precise and honest over clever.
• Present top-down → bottom-up → space-optimized as a deliberate arc, and volunteer the loop-direction / base-case traps by name. The person who says "descending capacity, or I'd be solving unbounded by accident" has clearly done this before.
• Know when it's NOT DP. "Generate all subsets/permutations" is backtracking (guide 04) — no overlap, so no memo. "Reachability / min jumps" is greedy (§3). "Best local choice after sorting" is greedy. Reaching for a table where greedy suffices is an over-engineering ding.
• Offer reconstruction proactively. If the prompt might want the actual coins/subsequence/path, mention you can recover it with a parent-pointer array and note it blocks full space-optimization — that tradeoff is the senior beat.

Cheat-sheet#

Self-test#

1. State the four things every DP is, and run all four on House Robber in one breath.
2. What single property separates a DP from plain backtracking, and how do you check for it before writing any table?
3. Convert naive Fibonacci to top-down, bottom-up, and O(1) space. At which step does space optimization become possible, and why?
4. Give the constraint→state heuristic: what does n ≤ 20, n ≤ 400, n,m ≤ 1000, n ≤ 10⁵ each imply about the likely DP?
5. In a rolled knapsack, why does 0/1 iterate capacity descending and unbounded ascending? What silently happens if you flip 0/1 to ascending?
6. Coin Change 2 vs Combination Sum IV: which loop is outer in each, why does that flip combinations↔permutations, and what are the two answers for coins=[1,2], amount=3?
7. Why must Dungeon Game be filled from the destination backward? What breaks in a forward sweep?
8. Give both LIS algorithms. In the O(n log n) version, what exactly is tails[k], and why is tails itself not a valid subsequence? What changes for non-strict LIS?
9. Write the edit-distance recurrence including base cases. Which initialization do people forget?
10. Explain the Burst Balloons reframe: why "last balloon to burst," not first? What does k mean and what are its neighbors?
11. In Binary Tree Max Path Sum, what value is returned up vs recorded in the global, and why can't you return the recorded one?
12. Why is Integer.MAX_VALUE a dangerous "impossible" sentinel in min-DPs, and what do you use instead for coin change vs TSP?
13. You memoized a recursion and it now returns wrong answers where the plain recursion was right. What's the one-line diagnosis?
14. Give two reconstruction techniques (value → actual solution) and the space tradeoff each imposes.
15. Name three problems that look like DP but should be greedy or backtracking instead, and say why.

Lineage / sources#

Dynamic programming is Richard Bellman's (1950s, RAND) — the "principle of optimality" and the name itself. The state/transition/base/order framing, memoization-vs-tabulation, and the knapsack/LCS/edit-distance/matrix-chain treatments are standard CLRS (Introduction to Algorithms, ch. 14–15). Kadane's algorithm is Jay Kadane (c. 1984). Edit distance is Wagner–Fischer (1974), itself from Levenshtein (1965) and Vintsyuk (1968). The O(n log n) LIS is patience sorting (Hammersley; Aldous–Diaconis) via Robinson–Schensted; LCS speedups trace to Hunt–Szymanski (1977). Held–Karp (1962) is the bitmask TSP. Burst Balloons, Dungeon Game, and the combinations-vs-permutations knapsack pair are LeetCode-canonical (LC 312, 174, 518/377). The pattern taxonomy and recognition cues (1-D/2-D/knapsack/interval/bitmask/tree DP) follow Grokking the Coding Interview (DesignGurus/Educative) and NeetCode 150/250; problem numbers reference LeetCode (5, 10, 44, 53, 62, 63, 64, 70, 72, 91, 96, 115, 120, 121, 139, 152, 174, 198, 213, 221, 279, 300, 312, 322, 337, 343, 377, 416, 494, 516, 518, 542, 646, 647, 674, 718, 746, 887, 1049, 1143). Interview-format and rubric notes (round mix by level, the "simulate a system"/DP+graph tilt at infra shops like Snowflake, the four scoring axes) come from Tech Interview Handbook, interviewing.io's 100K-interview study, and the 2025-26 vendor guides synthesized in the series playbook (00); treat exact round counts and Snowflake specifics as typical-not-guaranteed. For the internals and complexity of every structure used here as a tool — HashMap, ArrayList, primitive arrays, boxing and cache behavior — see the companion data-structures-java-kotlin-study-guide.md.