本文共 1337 字,大约阅读时间需要 4 分钟。
原贴地址:
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]输出: 0解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10] 输出: 1
注意:
你可以假设:
这个题非常简单,我们直接用dp的思想去思考即可。
状态量只有一个,就是金额,也就是说,我们对总金额amount进行dp即可。 dp[i]自然表示的就是总金额为i元时的方案数。 递推公式也很好出,dp[i] += dp[i - coins[t]]这里有没有发现一个问题,递推式其实跟题目中的某一句话没有关系,”每一种面额的硬币有无数个“,不管硬币的数量有多少,或者是只有一个,我们的递推公式都没有任何变化。
那么如果有之前做过这两类题目的同学,应该就能知道区别了,每一种有无限个,我们从前向后遍历dp数组,每种只有一个的时候,我们从后向前遍历dp数组。
虽然递推式都是dp[i] += dp[i - coins[t]]不变的。
这一点非常关键。
class Solution { public: int change(int amount, vector & coins) { vector dp(amount + 1); dp[0] = 1; for (auto & coin : coins) for (int i = 0; i <= amount - coin; ++i) dp[i + coin] += dp[i]; return dp[amount]; }};
impl Solution { pub fn change(amount: i32, coins: Vec) -> i32 { let amount = amount as usize; let mut v = vec![0; amount + 1]; v[0] = 1; for coin in coins { for i in 0..=(amount as i32 - coin) { v[(i + coin) as usize] += v[i as usize]; } } v[amount] }}
转载地址:http://duuci.baihongyu.com/