#322 零钱兑换(动态规划)

322. 零钱兑换 - 力扣（LeetCode）

注意跳过dp[x]=-1的

class Solution {
public:
    static bool comp(int a,int b){
        return a>b;
    }
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(),coins.end(),comp);
        vector<int> dp(amount+1,0); //dp[i]: the amount of coins needed to reach i
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            bool access=0;
            int min_amount=0x7fffffff;
            for(auto x:coins){
                if(i>=x && dp[i-x]!=-1){
                    access=1;
                    if(dp[i-x]<min_amount) min_amount=dp[i-x];
                }
            }
            if(!access) dp[i]=-1;
            else dp[i]=min_amount+1;
        }
        return dp[amount];
    }
};