Micro-questions over the 1-D DP module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. House robber
1. State the problem.
Answer
Houses in a row, each with some money. You cannot rob two adjacent houses. Maximise the total.
2. What question produces the state?
Answer
At house , what are my options? Rob it, or skip it. That is the entire problem.
3. Give state, transition and base.
Answer
STATE: best[i] = most money obtainable from houses .
TRANSITION: best[i] = max(best[i-1], best[i-2] + nums[i]).
BASE: best[0] = nums[0], best[1] = max(nums[0], nums[1]).
4. Justify the transition in words.
Answer
Skipping house leaves the best for ; robbing it adds nums[i] to the best for , since is now forbidden.
5. On [2,7,9,3,1], best[3] = 11, unchanged from best[2]. What does that mean?
Answer
House 3 holds 3, and robbing it would mean giving up house 2’s 9. A cell whose value equals its predecessor is the table telling you “skip” won — and that observation is what makes reconstruction possible.
6. Write the -space version.
Answer
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev17. What does that version handle for free?
Answer
The empty list and the single-element list, which the array version needs explicit guards for — a small illustration that space optimisation occasionally simplifies rather than complicates.
B. Coin change
8. State the problem.
Answer
Coins of given denominations, unlimited supply. Make an exact amount with the fewest coins, or report impossibility.
9. What is the decision at amount ?
Answer
Which coin do I use last? You do not know, so you try all of them.
10. Give state, transition and base.
Answer
STATE: best[a] = fewest coins summing to exactly .
TRANSITION: best[a] = 1 + min(best[a - c]) over every coin .
BASE: best[0] = 0; everything else starts at infinity.
11. Why does the infinity sentinel matter?
Answer
For coins and amount 3, no combination works and best[3] stays infinite — which is how the algorithm reports impossibility rather than returning a wrong small number.
12. What must you never initialise it to?
Answer
Zero. Use a real infinity, or a value provably larger than any valid answer (amount + 1 works).
13. How do you recover which coins, not just how many?
Answer
Record the decision alongside each cell — choice[a] = c when the cell improves — then walk backwards from amount, subtracting each recorded coin.
14. How general is that pattern?
Answer
Store the decision, walk it backwards — it is how every DP recovers a solution rather than a value, and it costs one array and no extra time.
15. What is the complexity, and what is the catch?
Answer
for amount and coins — but it is pseudo-polynomial: linear in the value of the amount, not its digit count. An amount of is infeasible even though it is a small input to type.
C. Longest increasing subsequence
16. The obvious state is “lis[i] = longest increasing subsequence within nums[0..i]”. What goes wrong?
Answer
You cannot write the transition. To decide whether nums[i] extends the best subsequence in , you need to know what that subsequence’s last element was — and the state does not record it.
17. State the diagnosis precisely.
Answer
The state is not wrong because it is imprecise. It is wrong because it is not enough information to compute the next state from. That is the general test for a candidate state — the single most transferable idea in this folder.
18. Give the fixed state, transition, base and answer.
Answer
STATE: lis[i] = longest increasing subsequence ending exactly at index .
TRANSITION: lis[i] = 1 + max(lis[j]) over with nums[j] < nums[i]; else 1.
BASE: every lis[i] starts at 1.
ANSWER: max(lis), not lis[n-1].
19. Why is the answer max(lis)?
Answer
Because the state pins the ending position, no single cell holds the global answer — you scan for it. That is a recurring consequence of pinning something in the state, and forgetting it is a common bug.
20. What is the complexity?
Answer
states × transition = .
D. The version
21. What is tails[k]?
Answer
The smallest possible tail value of any increasing subsequence of length . For each element, binary-search its position and overwrite; the answer is len(tails).
22. On [10,9,2,5,3,7,101,18] the tails array is [2,3,7,18]. Is that the LIS?
Answer
No. 3 appears before 5 in the LIS but after it in the array, and 18 comes after 101. Only the length of tails is meaningful.
23. What do you need to recover the actual subsequence?
Answer
An extra predecessor array. The DP gives it directly.
24. State the general lesson.
Answer
An asymptotically better algorithm is not automatically the one to use. If you need the subsequence and is small, the DP is simpler and gives you more.
E. The shared pattern
25. Give the state and transition for all four 1-D problems.
Answer
| Problem | State | Transition |
|---|---|---|
| Climbing stairs | ways to reach step | |
| House robber | best from houses | |
| Coin change | fewest coins for | |
| LIS | longest ending at |
26. What is every one of them?
Answer
Define what one cell means, then build it from cells with a smaller index. The differences are only in what “smaller” means and how many earlier cells the transition consults — two for stairs, all of them for LIS.
27. State the question that generates the state every time.
Answer
“What decision do I make at index , and what do I need to know to make it?”
28. Apply it to all three.
Answer
House robber: rob or skip, and you need the best totals two steps back. Coin change: which coin last, and you need every smaller amount. LIS: extend or start fresh, and you need the last element — which is why it goes into the state.
F. Traps
29. How do you test a candidate state?
Answer
Try to write the transition. If you need a fact the state does not record, the state is wrong.
30. What is the house robber base-case off-by-one?
Answer
best[1] = max(nums[0], nums[1]), not nums[1] — with one house you take it, with two you take the better. The rolling version sidesteps this by starting both accumulators at 0.
31. What can two variables never tell you?
Answer
Which houses were robbed. Do not space-optimise before you know whether you need the solution.
32. Summarise the module in one sentence.
Answer
Ask what decision you make at index and what you need to know to make it — that answer is the state, and if you cannot write the transition from it, you have the wrong one.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Classic One-Dimensional DP — the module
- Memoisation & Tabulation — Question Bank
- Classic Two-Dimensional DP — Question Bank
Software engineering
Infrastructure & security
Computer science
Hardware & engineering