Visualize the Coin Change problem step by step. Watch a DP table fill from 0 to the target amount, then backtrack to reveal the minimum set of coins.
Given coin denominations and a target amount, find the minimum number of coins needed. A classic DP problem that shows why greedy fails and how bottom-up tabulation always finds the optimal answer.
Greedy always picks the largest coin first. With coins [1, 3, 4] and target 6: greedy picks 4+1+1 = 3 coins. DP finds 3+3 = 2 coins. The optimal substructure of this problem requires DP, not greedy.
Build a 1D array dp[0..amount]. dp[a] = minimum coins to make exactly amount a. Start with dp[0] = 0 (zero coins for amount 0) and dp[1..amount] = ∞ (unknown).
For each amount a (1..amount), try every coin c. If a ≥ c and dp[a−c] + 1 beats dp[a], then dp[a] = dp[a−c] + 1 and last[a] = c. The "+1" means "use one coin of denomination c"; last[a] stamps the coin that finished a.
After filling the table, walk back by the stamps: amount → amount − last[amount] → … → 0. Each hop is one coin of the answer. This is why we stamp which coin finished each cell.
A = target amount, C = number of coin denominations. If no combination can make the amount, dp[amount] stays at ∞ and the answer is −1 (impossible).