Loading…
Loading…
The fewest coins for an amount — and the table that proves the greedy answer can be wrong.
Coins: 1 · 3 · 4
Row ∅ allows no coins: only the amount 0 is reachable (with 0 coins). Everything else is impossible, shown as −1.
1int coinChange(int[] coins, int A) {2 int m = coins.length, INF = Integer.MAX_VALUE / 2;3 int[][] dp = new int[m + 1][A + 1];4 for (int[] row : dp) Arrays.fill(row, INF);5 for (int i = 0; i <= m; i++) dp[i][0] = 0;6 for (int i = 1; i <= m; i++)7 for (int x = 0; x <= A; x++) {8 dp[i][x] = dp[i-1][x];9 if (coins[i-1] <= x)10 dp[i][x] = Math.min(dp[i][x],11 1 + dp[i][x - coins[i-1]]); // same row — an unlimited supply of coin i12 }13 return dp[m][A] >= INF ? -1 : dp[m][A];14}