Coin Change (Unbounded)

Various, 1972

The unbounded coin-change DP is textbook folklore popularized in algorithm courses and early dynamic programming expositions from the 1970s onward. For each amount w and each coin value, the recurrence relaxes dp[w] using dp[w − coin] + 1. The ribbon shows dp[0…amount], advancing sum by sum with the active coin in teal captions; the target cell turns coral when the table is complete.