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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes