Micro-questions over the DP recognition module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. State dynamic programming in one sentence.
Answer
Recognise that a recursion is recomputing, and stop it.
2. Where is the actual skill?
Answer
The technique is trivial once you see it. The skill is deciding whether it applies — and for that there are exactly two questions.
3. Why is the name unhelpful?
Answer
Bellman chose it in the 1950s partly because it sounded impressive to a research sponsor. It means neither “dynamic” nor “programming”. Read it as “careful recursion with a cache”.
B. The vocabulary
4. What is a subproblem, and what act is identifying one?
Answer
A smaller instance of the same problem. Identifying what counts as a subproblem is the same act as choosing the state.
5. What are overlapping subproblems, and what is notable about the property?
Answer
The recursion solves the same subproblem more than once. It is measurable — count total calls and distinct arguments and compare.
6. What is optimal substructure?
Answer
An optimal solution to the whole is built out of optimal solutions to its subproblems. Without it, caching sub-answers is useless because they cannot legitimately be combined.
7. Memoisation versus tabulation?
Answer
Memoisation caches results as the recursion runs — top-down, shape unchanged, you add a dictionary. Tabulation fills a table in a deliberate order with loops — bottom-up, no recursion.
8. What is the state space, and what does it give you?
Answer
The set of distinct subproblems. Its size times the cost of one transition is the complexity of the DP — which is how you predict the cost before writing anything.
C. Measuring overlap
9. What should you do instead of guessing?
Answer
Instrument the recursion, count total calls and distinct arguments, and divide.
10. What is fib(30)’s redundancy?
Answer
2,692,537 calls over 31 distinct subproblems — 86,856×.
11. What is merge sort’s redundancy, and why?
Answer
Exactly 1.0 — every recursive call receives a different slice, so no subproblem is ever repeated.
12. What follows about memoising merge sort?
Answer
It would add hashing and storage and save nothing. That is why merge sort is divide and conquer, not DP, despite both being recursive.
13. State the overlap test.
Answer
If distinct subproblems total calls, you have overlap, and memoisation collapses the exponential tree into a linear or polynomial walk over the state space.
D. Optimal substructure
14. Why does shortest path have it?
Answer
Every subpath of a shortest path is itself a shortest path — if it were not, you could substitute the better subpath and improve the whole, contradicting optimality.
15. What does that property enable?
Answer
It is precisely what lets Dijkstra and Floyd–Warshall compose sub-answers.
16. Show that longest simple path lacks it.
Answer
On the lab’s graph: longest A→D = 3, longest A→B = 3, longest B→D = 3. Composing gives 6, but the true longest A→D is 3 — the composed walk repeats a vertex.
17. State the failure precisely.
Answer
The sub-answers are each optimal and mutually incompatible. The best A→B uses up C and D; the best B→D needs them again. So no DP formulation exists — and longest simple path is NP-hard.
18. State the test for optimal substructure.
Answer
Take an optimal solution and cut it in half. Is each half optimal for the subproblem it solves? If forcing a half to be optimal can make the whole worse, you do not have it.
E. Greedy versus DP
19. Coins , amount 6. What does greedy give, and what is optimal?
Answer
Greedy: = three coins. Optimal: = two.
20. Does that mean coin change lacks optimal substructure?
Answer
No. If the optimal solution for 6 uses coin , the rest is an optimal solution for — and it is: the 2-coin solution uses a 3, and is optimal for amount 3.
21. What does greedy assume that is stronger and false?
Answer
That you can determine which coin to use by a local rule, without solving the subproblems. Optimal substructure says the sub-answers compose; it does not say which sub-answer to compose with.
22. State the difference in one line.
Answer
DP tries every coin and lets the table decide; greedy guesses and commits.
23. Greedy is right for US coins and wrong for . What follows?
Answer
Nothing about the problem statement tells you which case you are in — which is why “greedy feels right” is not an argument.
F. The grid
24. Give the four-cell grid.
Answer
| Overlapping? | Optimal substructure? | Technique |
|---|---|---|
| no | yes | divide and conquer |
| yes | yes | dynamic programming |
| yes | no | no efficient method known (NP-hard) |
| no | no | brute force / backtracking |
25. What is the fifth case?
Answer
Inside row two: when a local rule provably picks the right subproblem, skip the table and use a greedy algorithm — faster, but it needs a proof, not a feeling.
G. Traps
26. What if the state space is exponential?
Answer
Memoising an exponential recursion gives you an exponential DP. Caching does not create efficiency; it only removes redundancy.
27. What is the “sounds similar” trap?
Answer
Assuming optimal substructure by analogy. Shortest path has it; longest simple path does not, and they differ by one word.
28. Summarise the lesson in one sentence.
Answer
Measure the redundancy and check that optimal halves compose — overlap plus optimal substructure is DP, overlap alone is nothing, and substructure alone is divide and conquer.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- What Makes a Problem DP — the module
- Memoisation & Tabulation — Question Bank — the next bank
- When Greedy Works — the fifth case
Software engineering
Infrastructure & security
Computer science
Hardware & engineering