Coin Change

Start dumb — and notice greedy is a trap

“Fewest coins” whispers always grab the biggest coin. It even works for normal currency. But try coins = 1,3,4, amount = 6: greedy takes 4+1+1 — three coins — while 3+3 does it in two. Greedy commits to a big coin without knowing what mess it leaves behind. The honest fallback is trying every combination recursively, which explodes exponentially.

Find the bottleneck

Watch the recursion: to price amount 11 it prices 10, 9, and 6; pricing 10 re-prices 9 and 6 again… the same sub-amounts get solved over and over. The answer for each amount never changes — recomputing it is pure waste.

The optimal shape

1. dp[0] = 0 — paying nothing costs nothing. Everything else starts at a sentinel meaning “unreachable”.
2. For each amount 1..amount, try every coin that fits and keep the cheapest dp[a − coin] + 1.
3. dp[amount] still at the sentinel means no combination works: -1.

That’s O(amount × coins) time and O(amount) space. In the player below, the array is the dp table — watch each cell settle once and never change afterward, and watch which earlier cells (highlighted) each decision reads.

Watch it think

Run the default, then the greedy trap 1,3,4 | 6 (watch cell 6 pick 3+3), an unreachable target (2 | 3), and 1 | 0 — the base case as the entire answer.

1fun coinChange(coins: IntArray, amount: Int): Int {
2    val dp = IntArray(amount + 1) { amount + 1 }
3    dp[0] = 0
4    for (a in 1..amount) {
5        for (coin in coins) {
6            if (coin <= a) {
7                dp[a] = minOf(dp[a], dp[a - coin] + 1)
8            }
9        }
10    }
11    return if (dp[amount] > amount) -1 else dp[amount]
12}