零钱找零问题，题目是这样的

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return 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.

例如：

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

解决这样的问题，可以使用到的方法有贪心算法、暴力递归或lookback、动态规划算法。

贪心算法

如果对于某个总数一定有解，那么套用贪心算法，能很容易得到一个解决方法

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        count = 0
        rest = amount
        i = len(coins) - 1
        coins.sort()
        while i >= 0:
            curCount = rest//coins[i]
            rest -= coins[i] * curCount
            count += curCount
            if rest == 0:
                return count
            i -= 1
        return -1

过程：

• 先用最大的硬币来找零，用2个5元，剩下1元
• 使用2元硬币找零，发现只能用0个
• 最后使用1元硬币，可以用1个

总共最优使用3个硬币。这是贪心算法，最容易想到和使用的方法。这种情况算法复杂度是O(n)

lookback回溯

但是，可能有个问题，如果硬币面额比较多，可能用贪心算法，刚好得不到解，但是实际上是有解的。这种情况需要怎么办，需要使用回溯递归遍历。

    def coinChange(self, coins, amount):
        if not amount: return 0
        return self.dfs(coins, amount, amount)
        
    def dfs(self, coins, amount, rem):
        if rem < 0: return -1
        if rem == 0: return 0
        tempMin = amount + 1
        for coin in coins:
            res = self.dfs(coins, amount, rem - coin)
            if res and res < tempMin:
                tempMin = res
        return tempMin

这是一种回溯算法，使用了深度搜索方法，负责度也是指数级别的O(n^len(coins))，负责度比较高。

怎么优化呢，使用缓存，即备忘录优化，把中间结果缓存下来

def coinChange(self, coins, amount):
        if not amount: return 0
        return self.help(coins, amount, amount, [0]*(amount + 1))
        
    def help(self, coins, amount, rem, count):
        if rem < 0: return -1
        if rem == 0: return 0
        if count[rem-1] != 0: return count[rem-1]
        tempMin = amount + 1
        for coin in coins:
            res = self.help(coins, amount, rem - coin, count)
            if res and res < tempMin:
                tempMin = res
        count[rem-1] = -1 if tempMin == amount + 1 else tempMin
        return count[rem-1]

这种情况优化下来，复杂度也是O(n）的

动态规划

有没有更好的算法呢，那就是动态规划，动态规划满足：

• 重叠子问题：在穷举的过程中（比如通过递归），存在重复计算的现象；
• 无后效性：子问题之间的依赖是单向性的，某阶段状态一旦确定，就不受后续决策的影响；
• 最优子结构：子问题之间必须相互独立，或者说后续的计算可以通过前面的状态推导出来。

在解决过程中最重要的是写出动态转移方程：
coinchange的动态转移方程是:
dp[i] = min(dp[i], dp[i-coin] + 1)
指导状态转移方程，就很容易得到代码了：

    def coinChange_dp(self, coins, amount):
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(1, (amount + 1)):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
        return dp[amount] if dp[amount] <= amount else -1

这个算法复杂度就是O(n)了

小结

coinChange虽然比较简单，但是要想清楚其中问题的关键，还是要把所有可能的算法都思考一遍。特别是只用贪心算法，就会考虑不到有可能得不到解的情况；只有动态规划，可能就不知道怎么得来动态规划的。