【leetcode刷题】T166-零钱兑换编程题

示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [sys.maxsize] * (amount+1)
        dp[0] = 0
        coins.sort()
        for i in range(1, amount+1):
            for c in coins:
                if i - c < 0:
                    break
                else:
                    dp[i] = min(dp[i], dp[i-c] + 1)
        return dp[-1] if dp[-1] < sys.maxsize-1 else -1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount*10);
        dp[0] = 0;
        for(int i=1; i < amount+1; i++){
            for(auto c: coins){
                if(i - c < 0)
                    continue;
                dp[i] = min(dp[i], dp[i-c] + 1);
            }
        }
        return dp.back() > amount ? -1 : dp.back();
    }
};