LeetCode322零钱兑换2018_1207_1624

dp[i]代表要凑齐总数为i的钱所需要的最少硬币数
dp[i]=min(dp[i-coins[j]])+1 for all j

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

这里面考虑到有面值为1的硬币的情况
测试用例

不通过
dp[1]!=1,没有面值为1的硬币

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int min=0x7fffffff;
        vector<int> dp(amount+1,amount+1);  //amount+1为不可能需要的次数，凑不出时作为判断条件
        dp[0]=0;
       // dp[1]=1;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(i-coins[j]>=0&&dp[i-coins[j]]<amount+1){ //如果i-coins[j]能够凑出来
                    if(dp[i-coins[j]]<min)  min=dp[i-coins[j]];  
                }
            }
            if(min!=0x7fffffff)  dp[i]=min+1;  //如果能够凑出来
            min=0x7fffffff;
        }
        return dp[amount]==amount+1?-1:dp[amount];  
    }
};

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/qq_40200779/article/details/84879845
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-25 02:29:00
阅读 ( 684 )
分类：算法

LeetCode322零钱兑换2018_1207_1624

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看