322.零钱兑换

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

解法一：dp

用dp[n]表示找n元的最少硬币数 由用例coins = [1, 2, 5], amount = 11可知

    dp[6]      =   min(dp[1] + 1,      dp[4] + 1,         dp[5] + 1)
6块钱找零由     【1块钱的找法】+5块     【4块钱的找法】+2块    【5块钱的找法】+1块 三者的最小值决定

易出代码：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [sys.maxsize] * (amount+1)  #因为是求最小值，因此用∞为初值
        dp[0] = 0  #初始条件
        for i in range(1, amount+1):  #从1开始一次遍历
            for coin in coins:  #遍历所有硬币面值
                if i < coin:    #钱数比币值还小，跳过
                    continue
                #关键，状态转移方程，求所有币值凑成i元的最少硬币数
                dp[i] = min(dp[i], dp[i-coin] + 1)
        return -1 if dp[amount] == sys.maxsize else dp[amount]

初始条件改进

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        #初值不一定要为∞，选一个永远取不到的数也可
        #极端情况：若币值为1，找零硬币数最多，为amount，因此amount+1永远取不到
        dp = [amount+1] * (amount+1)    
        dp[0] = 0
        for i in range(1, amount+1):
            for coin in coins:
                if i < coin:
                    continue
                dp[i] = min(dp[i], dp[i-coin] + 1)
        return -1 if dp[amount] == amount+1 else dp[amount]