518. Coin Change 2

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int change(int amount, int[] coins) {
        // 定义 dp[i][j] 为前 i 个硬币，使用其中一些硬币可以凑成总金额 j 的组合数
        int[][] dp = new int[coins.length + 1][amount + 1];

        // 金额为 0 时前 i 个硬币，选择 0 个硬币均能组成，此时组合数为 1
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                for (int k = 0; j - k * coins[i - 1] >= 0; k++) {
                    dp[i][j] += dp[i - 1][j - k * coins[i - 1]];
                }
            }
        }

        return dp[coins.length][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
class Solution {
    public int change(int amount, int[] coins) {
        // 定义 dp[i][j] 为前 i 个硬币中使用一些硬币凑成总金额 j 的硬币组合数
        int[][] dp = new int[coins.length + 1][amount + 1];

        dp[0][0] = 1; // 前 0 个硬币只能凑成总金额 0, 即只有一种方案

        // 总金额 0 可以由前 i 个硬币中选择 0 个硬币构成，即只有一种方案
        for (int j = 1; j <= coins.length; j++) {
            dp[j][0] = 1;
        }

        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j]; // 不使用当前硬币
                // 使用当前硬币时，状态转移由数学公式推导而出
                if (j - coins[i - 1] >= 0) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }

        return dp[coins.length][amount];
    }
}

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

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

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

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

将 ② 式替换 ① 式中的部分项后得到化简后的 ① 式：
dp[i][j] = sum(dp[i - 1][j], dp[i][j - wi])

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j - coins[i - 1] >= 0) {
                    dp[j] += dp[j - coins[i - 1]];
                }
            }
        }

        return dp[amount];
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) { // 注意 coin 循环在外层
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

示例：amount = 4, coins = [1, 2], 第一层循环完成时：

dp[0] = 1, 组合：[]
dp[1] = dp[0] = 1, 组合：[1]
dp[2] = dp[1] = 1, 组合：[1, 1]
dp[3] = dp[2] = 1, 组合：[1, 1, 1]
dp[4] = dp[3] = 1, 组合：[1, 1, 1, 1]

第二层循环完成时：

dp[0] = 1, 组合：[]
dp[1] = 1, 组合：[1]
dp[2] = dp[2] + dp[0] = 2, 组合：[1, 1], [2]
dp[3] = dp[3] + dp[1] = 2, 组合：[1, 1, 1], [1, 2]
dp[4] = dp[4] + dp[2], 组合：[1, 1, 1, 1], [1, 1, 2], [2, 2]

coin 在外层循环保证了不会出现 [2, 1, 2] 这样的组合，即不会出现与 [1, 1, 2] 相同的组合。

References

518. Coin Change 2
『 一文搞懂完全背包 』从0-1背包到完全背包，逐层深入+数学推导