Lesson 20 — Coin change (DP)

Dynamic programming: small answers build big ones

Dynamic programming (DP) solves a big problem by first solving all the small versions and storing them in a table. For "fewest coins to make an amount", dp[a] = fewest coins for amount a. To fill dp[a], try every coin c: use one c, plus the best way to make a − c, which you already know.

best[t] = min(best[t], best[t - step] + 1)   # use one more step of this size

float("inf") (infinity) means "not possible yet".

Why it matters: DP solves route planning, text diffing and spell-check suggestions that brute force could never finish.