leetcode 322 Coin Change 完全背包

题目

https://leetcode.com/problems/coin-change/submissions/

思路

非常好的参考
https://zhuanlan.zhihu.com/p/141627678?from_voters_page=true
min 类型的完全背包问题,和零一背包的唯一区别在于 j 从 coins 开始,这样可以复用之间 的结果,该写法是状态压缩的写法

源码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp(amount+1,INT_MAX-10);
        dp[0] = 0;
        for(int i = 0;i < coins.size();++i){
            for(int j = coins[i];j <=amount;++j){
                if(dp[j] != INT_MAX)
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX-10?-1:dp[amount];
    }
};

发表评论

邮箱地址不会被公开。 必填项已用*标注