0518-零钱兑换 II

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

**输入：** amount = 5, coins = [1, 2, 5]
**输出：** 4
**解释：** 有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

**输入：** amount = 3, coins = [2]
**输出：** 0
**解释：** 只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

**输入：** amount = 10, coins = [10] 
**输出：** 1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

方法一：动态规划

这道题中，给定总金额 amount 和数组 coins，要求计算金额之和等于 amount 的硬币组合数。其中，coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题需要计算的是选取硬币的组合数。

可以通过动态规划的方法计算可能的组合数。用 dp}[x] 表示金额之和等于 x 的硬币组合数，目标是求 dp}[\textit{amount}]。

动态规划的边界是 dp}[0]=1。只有当不选取任何硬币时，金额之和才为 0，因此只有 1 种硬币组合。

对于面额为 coin 的硬币，当 coin} \le i \le \textit{amount 时，如果存在一种硬币组合的金额之和等于 i - \textit{coin，则在该硬币组合中增加一个面额为 coin 的硬币，即可得到一种金额之和等于 i 的硬币组合。因此需要遍历 coins，对于其中的每一种面额的硬币，更新数组 dp 中的每个大于或等于该面额的元素的值。

由此可以得到动态规划的做法：

  • 初始化 dp}[0]=1；

  • 遍历 coins，对于其中的每个元素 coin，进行如下操作：

    • 遍历 i 从 coin 到 amount，将 dp}[i - \textit{coin}] 的值加到 dp}[i]。

  • 最终得到 dp}[\textit{amount}] 的值即为答案。

上述做法不会重复计算不同的排列。因为外层循环是遍历数组 coins 的值，内层循环是遍历不同的金额之和，在计算 dp}[i] 的值时，可以确保金额之和等于 i 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。

例如，coins}=[1,2]，对于 dp}[3] 的计算，一定是先遍历硬币面额 1 后遍历硬币面额 2，只会出现以下 2 种组合：

\begin{aligned}
3 &= 1+1+1 \
3 &= 1+2
\end{aligned}

硬币面额 2 不可能出现在硬币面额 1 之前，即不会重复计算 3=2+1 的情况。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int Change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        foreach (int coin in coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i-coin]
        }
    }
    return dp[amount]
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
int change(int amount, int* coins, int coinsSize) {
    int dp[amount + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < coinsSize; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

复杂度分析

  • 时间复杂度：O(\textit{amount} \times n)，其中 amount 是总金额，n 是数组 coins 的长度。需要使用数组 coins 中的每个元素遍历并更新数组 dp 中的每个元素的值。

  • 空间复杂度：O(\textit{amount})，其中 amount 是总金额。需要创建长度为 amount}+1 的数组 dp。

 Comments
On this page
0518-零钱兑换 II