518. Coin Change 2
2020-06-09 本文已影响0人
铭小狮子酱
思路
动态规划
- 用一个数组
dp
存储结果,dp[i]
表示amount=i
时的组合数目。 - 初始态:
dp[0]=1
- 遍历所有
coin
,对每个coin
计算coin<=i<=amout
的dp
值
代码(cpp)
class Solution {
public:
int change(int amount, vector<int>& coins) {
// dp[i]: number of combinations with amount i
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for(auto& coin : coins){
for(int i = coin; i <= amount; i++)
dp[i] += dp[i - coin];
}
return dp.back();
}
};