322. Coin Change

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int MAX = 10001;

        // 定义 dp[i][j] 为在前 i 个硬币中选择部分硬币可组成金额 j 所需的最少硬币个数
        int[][] dp = new int[n + 1][amount + 1];

        // 使用前 i 个硬币可以组成金额 0, 即选择 0 个硬币
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }

        // 使用前 0 个硬币不能组成金额 j
        for (int j = 1; j <= amount; j++) {
            dp[0][j] = MAX;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = MAX;

                // 当前硬币使用 k 次
                for (int k = 0; j - k * coins[i - 1] >= 0; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k);
                }
            }
        }

        return dp[n][amount] == MAX ? -1 : dp[n][amount];
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int MAX = 10001;

        // 定义 dp[i][j] 为在前 i 个硬币中选择部分硬币可组成金额 j 所需的最少硬币个数
        int[][] dp = new int[n + 1][amount + 1];

        // 使用前 i 个硬币可以组成金额 0, 即选择 0 个硬币
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }

        // 使用前 0 个硬币不能组成金额 j
        for (int j = 1; j <= amount; j++) {
            dp[0][j] = MAX;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j]; // 当前硬币使用 0 次

                // 当前硬币使用多次，状态转移由数学公式推导而出
                if (j - coins[i - 1] >= 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
                }
            }
        }

        return dp[n][amount] == MAX ? -1 : dp[n][amount];
    }
}

设第 i 个硬币的价值为 wi，设我们最多可以使用 k 次该硬币：

  • 当不使用第 i 个硬币时，dp[i][j] = dp[i - 1][j]
  • 当使用 1 次第 i 个硬币时，dp[i][j] = dp[i - 1][j - wi] + 1
  • 当使用 2 次第 i 个硬币时，dp[i][j] = dp[i - 1][j - 2 * wi] + 2
  • 当使用 k 次第 i 个硬币时，dp[i][j] = dp[i - 1][j - k * wi] + k

易知：dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wi] + 1, dp[i - 1][j - 2 * wi] + 2, … dp[i - 1][j - k * wi] + k) ①

令 j = j - wi，因为少了一个 wi，所以能够使用的最大硬币数为 k - 1:
易知：dp[i][j - wi] = min(dp[i - 1][j - wi], dp[i - 1][j - 2 * wi] + 1, dp[i - 1][j - 3 * wi] + 2, … dp[i - 1][j - wi - (k - 1) * wi] + k - 1)
化简：dp[i][j - wi] = min(dp[i - 1][j - wi], dp[i - 1][j - 2 * wi] + 1, dp[i - 1][j - 3 * wi] + 2, … dp[i - 1][j - k * wi] + k - 1) ②

将 ② 式替换 ① 式中后面 k - 1 项后得到化简后的 ① 式：
dp[i][j] = min(dp[i - 1][j], dp[i][j - wi] + 1)

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int coinChange(int[] coins, int amount) {
        int MAX = 10001; // 注意 MAX 要使用 10001 而不是 10000, 否则 coins = [1], amount = 10000 不能 AC

        // 定义 dp[i] 为组成总金额 i 所需的最少的硬币个数
        int[] dp = new int[amount + 1];

        for (int i = 1; i < dp.length; i++) {
            dp[i] = MAX;
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == MAX ? -1 : dp[amount];
    }
}

References

322. Coin Change
剑指 Offer II 103. 最少的硬币数目