leetcode-322-零钱兑换

//注意但凡出现数组就要考虑越界

class Solution {

public:

    int coinChange(vector<int>& coins, int amount) {

        sort(coins.begin(), coins.end());

        int base = coins[0];

        if (amount == 0) return 0;

        if (amount < base) return -1;

        vector<int> dp(amount - base + 1, amount+1);

        for (auto c:coins) {

            if (c > amount) break;

            dp[c-base] = 1;

        }

        for (int i=1; i<dp.size(); i++){

            if (dp[i] != 1){

                for (auto c:coins){

                    if (c > i) break;

                    else {

                        dp[i] = min(dp[i], dp[i-c]+1);

                    }

                }

            }

        }

        if (dp.back() == amount+1) return -1;

        return dp.back();

                

    }

};