Leetcode 518. 零钱兑换 II (完全背包求方案数优化)

2020/11/17 08:49
阅读数 35

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // dp[i][j] 表示前i个硬币,凑成金额j的方案数
        // dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i]] + dp[i-1][j-2*coins[i]] + ... + dp[i-1][j-k*coins[i]]
        // dp[i][j-coins[i]] = ...
        // dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]
        vector<int> dp(amount+1);
        dp[0] = 1;
        for(auto coin:coins){
            for(int j=coin;j<=amount;j++){
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部