Micro-questions over the DP pattern note. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
This bank is about recognising recurrence shapes. The theory is in what makes a problem DP.
A. The value proposition
1. State DP’s entire value proposition.
Answer
Eliminating redundant recomputation — break a problem into overlapping subproblems, solve each exactly once, and reuse the answers.
2. What two properties must hold?
Answer
Overlapping subproblems (the same smaller question gets asked repeatedly) and optimal substructure (the best answer to the big problem is built from the best answers to its subproblems).
3. Without both, what do you have?
Answer
Plain recursion. DP is specifically the caching of that recursion’s repeated work.
B. The two applications
4. What is memoisation, in one line?
Answer
Top-down — keep the natural recursive structure, cache results the first time each subproblem is solved.
5. What is tabulation?
Answer
Bottom-up — build the answer iteratively from the smallest subproblems up, with no recursion at all.
6. Give the trade-off.
Answer
Bottom-up avoids call-stack overhead entirely; top-down is often easier to derive first, since it mirrors the natural recursive definition.
7. Fibonacci can beat . How, and should you?
Answer
via matrix exponentiation () or Binet’s closed form. Neither is worth reaching for by default — they are a footnote once DP stops being fast enough.
C. The real skill
8. What single question does every DP problem come down to?
Answer
How does the answer to a state depend on smaller states?
9. Fibonacci and Climbing Stairs share a recurrence. Why?
Answer
The question is structurally identical — dp[i] = dp[i-1] + dp[i-2] in both.
10. State what “getting good at DP” actually means.
Answer
Recognising that two differently-worded problems share a recurrence.
D. The six sub-patterns
11. Name all six and what distinguishes each.
Answer
Fibonacci-style — dp[i] depends on a fixed few previous states. 0/1 knapsack — subset under a capacity, each item once. LCS — two sequences, dp[i][j] from three neighbours. LIS — best ending at , depends on all earlier . Subset sum — knapsack variant asking only “does any subset hit the target?”. Matrix chain — dp[i][j] tries every split point between and .
12. How does NeetCode split them, and why is that split useful?
Answer
1-D DP (state is one index) versus 2-D DP (state is two indices — a grid or a pair of sequences). The dimension of the state is the first thing to decide.
E. 1-D
13. House Robber — recurrence and space?
Answer
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Only the last two states matter, so it collapses to space.
14. Coin change — which knapsack shape is it, and what is the recurrence?
Answer
Unbounded knapsack (coins reusable). dp[a] = 1 + min(dp[a - c]) over every coin .
15. Where exactly is the 0/1 versus unbounded distinction?
Answer
Entirely in the loop order. Reuse-allowed iterates capacity outermost; each-item-once iterates items outermost and capacity descending, so an item is not counted twice.
16. LIS — recurrence, cost, and the improvement?
Answer
dp[i] = 1 + max(dp[j]) over with nums[j] < nums[i] — . A binary-search-on-patience-piles trick gets it to .
F. 2-D
17. When does the table become 2-D?
Answer
When the answer depends on two moving parts — a position in a grid, or an index into each of two sequences.
18. Unique Paths — recurrence and base case?
Answer
dp[r][c] = dp[r-1][c] + dp[r][c-1] — each cell is reached from above or from the left. Base case: the first row and column are all 1.
19. LCS — the two branches?
Answer
Characters match → extend the diagonal, dp[i-1][j-1] + 1. They do not → take the better of dropping one character from either string.
G. Traps
20. What is the cost of reaching for DP without confirming overlap?
Answer
Memoisation adds overhead for no benefit — it is just plain recursion or divide and conquer. Merge sort is the canonical recursion without overlapping subproblems.
21. What is the most common DP bug?
Answer
Off-by-one errors in the base cases (dp[0], dp[1]). Get the smallest one or two states right by hand before trusting the recurrence for larger .
22. What is the usual space optimisation?
Answer
Keeping only the last row or last few states — often , or .
23. Summarise the pattern in one sentence.
Answer
Find the recurrence, decide whether the state is one index or two, and recognise that most problems are one of six shapes you have already seen.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Dynamic Programming Pattern — the pattern
- What Makes a Problem DP — Question Bank
- Classic 1-D DP — Question Bank
- Classic 2-D DP — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering