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
noyesdivide and conquer
yesyesdynamic programming
yesnono efficient method known (NP-hard)
nonobrute 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Dynamic Programming