Dynamic programming: multiple-choice review
Multiple-choice synthesis across the DP unit: when DP applies, memoization vs tabulation, state design, classic recurrences, and the complexity each one buys.
Six 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.
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.
A problem splits into subproblems, and you confirm those subproblems repeat. Is that enough to justify a DP solution?
You have a working memoized (top-down) solution. When is rewriting it as tabulation (bottom-up) worth the effort?
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?
0/1 knapsack runs in O(n*W) time. Why is this called pseudo-polynomial rather than polynomial?
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?
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?
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.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.