参考 [LeetCode] Coin Change 硬币找零

题目描述：You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

题目解析：

这道题目有一点不同于动态规划_实战1中的硬币找零的问题，这道题中的硬币数，不一定是[1,2,5]这样能够把所有硬币都能找零的，还可能存在根本不能找零的情况（这一点待会再分析解决办法）。

对于求极值问题，我们还是先考虑用DP来做，同实战1中的硬币找零问题一样，我们维护一个动态一维数组，求中dp[i]表示钱数为i时的最小硬币的找零。
对于满足条件的每一个硬币，状态转移方程为：

dp[i] = min(dp[i], dp[i - coins[j]] + 1)

从上面式子，可知，我们需要给dp[i]赋一初值，这个初值赋值为可能的最大值。也就是需要找零的面额amount+1的值。如果存在能够进行找零的情况，那么最终的dp[i]的值一定是比amount+1少的。

那么如果不存在能够找零的情况呢？
比如对于coins = [2]，amount = 9的情况。是一定不存在找零情况的。
那么进行动态规划的时候，自底向上，遇到1,3,5,7的情况会怎么样呢？
**还是按照上面的式子，我们会发现，遇到9的时候，会减2，到7中找结果。而7的结果从5,3,1得来，结果是amount+1+1=amount+2。这样进行比较得到的最小值，就还是amount+1。

一维数组中，如果值是amount+1，就说明这个面额是不存在找零情况的。因此，对于amount不能找零，只需要在最后判断一下是不是等于amount+1即可，如果等于就返回-1,。

需要注意的地方

第一点：
在一开始初始化数组的时候，我采用的是这三行代码：

        result = []
        for i in range(amount+1):
            result.append(amount+1)

但是在LeetCode上运行超时了。
参考别人的代码，是这么初始化一维数组的：

result = [amount] * (amount)

第二点：
因为硬币数是1,2,5类似的，而自底向上进行遍历时，Python是从0到n-1进行遍历的。所以，最好将一维数组与实际情况统一起来。res[0] = 0，代表的就是找零面额为0的情况。遍历，从1到n+1进行遍历。

代码实现：

class Solution:
    def coinChange(self,coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """

        #这一点也有点坑，不过append确实会增加时间复杂度？
        #全部取值为amount+1是一个小技巧，有利于后面的比较
        result = [amount] * (amount)
            
        result[0] = 0
        for i in range(1,amount+1):
            for j in coins:
                if i >= j:
                    result[i] = min(result[i],result[i-j] + 1)

    #         print('i',i)
        if result[amount] == amount+1:
            return -1
        else:
            return result[amount]