Card 1 / 7
Dynamic Programming applies when a problem has two properties:
When you spot both, you can store solutions to subproblems and reuse them instead of recomputing.
Ask yourself: "If I solve this recursively, will I compute the same thing twice?" If yes, DP might help.
Which of these problems have both overlapping subproblems and optimal substructure — the two pillars that make DP apply?
fib(n) splits into fib(n-1) and fib(n-2), and the same calls repeat all over the recursion tree — overlapping subproblems with optimal substructure.
The best way to make 30¢ builds on the best way to make smaller remainders, and different coin choices reach the same remainders again and again — both pillars hold.
Each halving discards the other half for good: one subproblem, never revisited. Nothing overlaps, so there is nothing to cache — plain divide and conquer.
It has optimal substructure (sort the halves, merge), but the two halves are disjoint — no subproblem is solved twice, so memoization would find nothing to reuse.
Card 2 / 7
Naive recursive Fibonacci looks elegant but hides exponential work:
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2) ← computed here
│ │ └── fib(1)
│ └── fib(2) ← and here again!
└── fib(3) ← this entire subtree repeats!