Algorithms from zero
Dynamic programming: multiple-choice review
Crux Multiple-choice synthesis across the DP unit: when DP applies, memoization vs tabulation, state design, classic recurrences, and the complexity each one buys.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySix questions that cut across the whole unit. Each one mirrors a decision you make at the start of a real DP problem — not a definition to recite, but which property to check, which state to pick, and what complexity it costs.
Goal
Confirm you can connect the two enabling properties, the two implementation styles, state design, and the classic recurrences — the synthesis the individual lessons built toward.
Quiz
Completed
A problem splits into subproblems, and you confirm those subproblems repeat. Is that enough to justify a DP solution?
Heads-up Overlapping subproblems justify caching, but DP needs both properties. Without optimal substructure there is no correct recurrence to combine subanswers, so memoizing a wrong recurrence just caches wrong answers fast.
Heads-up That describes divide and conquer (e.g. merge sort), not DP. DP is precisely the case where subproblems DO overlap, which is why a cache pays off.
Heads-up If a greedy choice provably works you often do not need DP at all. DP is the tool for when local greedy choices fail but optimal substructure still holds.
Quiz
Completed
You have a working memoized (top-down) solution. When is rewriting it as tabulation (bottom-up) worth the effort?
Heads-up Both compute each distinct state once, so they share the same asymptotic time. Tabulation wins on constants, stack safety, and space optimization, not on big-O.
Heads-up Memoization's sparse-state advantage is real, but it is not always preferable: deep recursion overflows the stack and a hash-map cache costs more per access than an array. The choice is a tradeoff, not absolute.
Heads-up Every DP has base cases; that is unrelated. Tabulation specifically requires you to know an iteration order that fills cells before they are read.
Quiz
Completed
For House Robber, the recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). What does each branch encode, and why is two indices of history enough?
Heads-up It is the reverse. dp[i-1] is the best when you do NOT take house i; dp[i-2]+nums[i] is the best when you DO take it, since taking i forbids i-1.
Heads-up The adjacency constraint is local: taking i only forbids i-1. So dp[i] reads only dp[i-1] and dp[i-2], and two rolling variables replace the whole array.
Heads-up Robbing alternate houses fails on inputs like [2,1,1,2]; the optimum takes houses 0 and 3. The max over the two branches is exactly why DP beats greedy alternation.
Quiz
Completed
0/1 knapsack runs in O(n*W) time. Why is this called pseudo-polynomial rather than polynomial?
Heads-up The memoized or tabulated version computes each state once — it is not exponential in the number of states. Pseudo-polynomial refers to the dependence on the magnitude of W, not branching.
Heads-up O(n*W) is the worst case of the DP, not an average. The 2^n figure is the naive recursion without memoization.
Heads-up W being prime is irrelevant. The pseudo-polynomial label is purely about W being a value whose encoding length is logarithmic.
Quiz
Completed
The O(n log n) Longest Increasing Subsequence algorithm maintains a 'tails' array. What is the answer to the problem, and what does the tails array actually contain?
Heads-up Tails is not a real subsequence — each slot is overwritten with the smallest tail for that length, so the stored values may not even appear in order in the input. Only its length is meaningful.
Heads-up The maximum stored value is just the largest element placed; it has no relation to the LIS length. The number of slots used is the answer.
Heads-up That is the O(n^2) DP's array, not tails. The tails array is indexed by subsequence LENGTH, not by input position, which is what enables the binary search.
Quiz
Completed
Interval DP (matrix chain, burst balloons) iterates by increasing interval length and picks a split point k inside [i..j]. Why iterate by length rather than the usual left-to-right i?
Heads-up It is a correctness requirement, not style. A left-to-right i-loop reaches dp[i][j] before dp[i+1][j-1] is filled, reading garbage. The dependency is on shorter intervals, so length must be the outer loop.
Heads-up It has a clear base case: length-1 (or length-0) intervals. Those are exactly the shortest intervals filled first when you iterate by length.
Heads-up k ranges over every position inside the interval; you take the best over all splits. Fixing k to the midpoint would break optimality — the optimal last action is rarely the middle.
Recap
The through-line of the unit is one checklist you run before writing any DP: confirm overlapping subproblems AND optimal substructure; design the smallest state that captures the decision (one index for House Robber, two for knapsack and LCS, an interval for matrix chain); pick memoization or tabulation by stack depth and space needs, not big-O; and know what the table really holds — including the LIS tails array, whose length, not contents, is the answer. Same complexity either way: states times work per state.