题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明: 你可以认为每种硬币的数量是无限的。

我的解法——DP（AC）

子问题：DP[i]：凑的amount为i时，所需的最少硬币个数。
递推：见代码
一开始内循环想成需要遍历amount了，其实这里遍历coin即可。
时间复杂度O(mn)，空间复杂度O(n)，其中n是amount，m是货币数目
Beat70%

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if(amount == 0):return 0
        
        dp = [-1] * (amount + 1)
        
        for corn in coins:
            if(corn <= amount):
                dp[corn] = 1
        dp[0] = 1
        
        for i in range(1, amount + 1):
            res = i
            flag = False
            for coin in coins:
                if(coin <= i and dp[coin] != -1 and dp[i - coin] != -1 and res >= dp[coin] + dp[i - coin]):
                    flag = True
                    res = dp[coin] + dp[i - coin]
            if(flag and dp[i] == -1):
                dp[i] = res
            
            # print(dp)
        return dp[amount]
        

参考答案

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