Đang tải…
Đang tải…
Số đồng ít nhất cho một số tiền — và cái bảng chứng minh rằng đáp án greedy có thể sai.
Mệnh giá: 1 · 3 · 4
Hàng ∅ không cho dùng đồng nào: chỉ số tiền 0 là đạt được (với 0 đồng). Mọi ô khác là bất khả, hiển thị −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]]); // cùng hàng — đồng i có số lượng không giới hạn12 }13 return dp[m][A] >= INF ? -1 : dp[m][A];14}