Dynamic programming fundamentals

For OVERLAPPING subproblems: compute each once, remember it. DP = recursion + memory.

The problem with naive recursion

• Fewest coins for a = 1 + min over coins of (fewest for a−c)
• Same subamounts recur across branches → exponential recomputation
• Fibonacci: fib(5) computes fib(2) three times → O(φⁿ)
• The subproblems OVERLAP, and naive recursion is blind to it

Two styles, same table

• Top-down (memoize): the recurrence + a cache; @lru_cache does it free
• Bottom-up (tabulate): fill dp[0..n] from the smallest up, no recursion
• Both: each subproblem computed ONCE → O(amount × #coins)
• Needs optimal substructure + overlapping subproblems

Watch the table fill

dp[a] = 1 + min(dp[a−1], dp[a−3], dp[a−4]). Every cell consulted is already done. dp[6] = 2 (3+3) — where greedy's 4+1+1 = 3 went wrong.

Exponential → polynomial

Amount 20: naive 38,000 calls, DP 60 → 640× less. DP changes the complexity CLASS.

Takeaway

The hard part is defining the STATE + recurrence; memoization is mechanical. Solves what greedy can't (greedy wrong 13% here) by considering all choices. Next: knapsack — the DP greedy provably can't crack.