题目链接
题目描述
给你一个整数数组 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
解题思路
方法一:动态规划(完全背包组合问题 组合问题求组合数,不考虑顺序问题)
动态规划的边界是 dp[0]=1。只有当不选取任何硬币时,金额之和才为 0,因此只有 1 种硬币组合。
对于面额为 coin 的硬币,当 coin≤i≤amount 时,如果存在一种硬币组合的金额之和等于 i−coin,则在该硬币组合中增加一个面额为 coin 的硬币,即可得到一种金额之和等于 i 的硬币组合。因此需要遍历 coins,对于其中的每一种面额的硬币,更新数组 dp 中的每个大于或等于该面额的元素的值。
- 初始化 dp[0]=1;
- 遍历 coins,对于其中的每个元素 coin,进行如下操作:
- 遍历 i 从 coin 到 amount,将 dp[i−coin] 的值加到 dp[i]。
- 最终得到 dp[amount] 的值即为答案。
上述做法不会重复计算不同的排列。因为外层循环是遍历数组coins 的值,内层循环是遍历不同的金额之和,在计算 dp[i] 的值时,可以确保金额之和等于 i 的硬币面额的顺序,由于顺序确定,因此不会重复计算不同的排列。
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1);
dp[0] = 1;//一个也不选也是一种方案
for(const int coin : coins){ //nums循环
for(int i=coin;i<=amount;i++){ // target循环
dp[i] += dp[i-coin];//组合问题状态转移方程 dp[i]代表达到金额i的组合数
}
}
return dp[amount];
}
};
- 时间复杂度 O(nm)
- 空间复杂度 O(n)