问题描述

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:coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:coins = [2], amount = 3
return -1.
Note:You may assume that you have an infinite number of each kind of coin.

思路分析

一道medium的题目没想到我做得这么曲折，很有必要记录一下。
以下设coins数组长度为k，infinity = amount+1。

1. 思路1：非常暴力的动规
   看到题目首先想到的是动态规划，如何动态规划呢？我的思路是用一个amount+1 x k的数组f进行记录，首先初始化最后一列，当i%coins[k-1]等于0时，f[i][k-1]=i/coins[k-1]，否则为inifity，转移函数f[i][j] = min{p+f[i-p x coins[j]][j+1]}，其中0<=p<=i/coins[j]。这样做的问题在于，对于每个单元格的计算是一个循环，时间成本大，结果TLE。
2. 思路2：正经的动规
   参考了LeetCode Discuss中的写法，它只记录一个长度为amount+1的一维数组f，初始化f[0] = 0，其他值为infinity， f[i] = min{1+f[i-coins[j]]，f[i]}，其中0<=j<k并且保证i-coins[j]>=0。
   这样做的结果 Runtime: 1792 ms, which beats 15.38% of Python submissions.
   
   Paste_Image.png
   
   动规已经无法简化了，但排名还是如此靠后有木有！我就惊呆了，一直以为动规是非常简单快速的方法！
3. 思路3：分支定界
   搜索啊搜索。思想很简单，建一个k层的搜索树，注意回溯条件和界的更新就好了，结果 Runtime: 192 ms, which beats 98.94% of Python submissions.
   
   Paste_Image.png
   
   结果让我挺惊讶的，没想到对于这道题分支定界比动规快辣么多，带剪枝的搜索威力好大，想想也对，毕竟人工智能里好多α-β剪枝的应用。

AC代码

思路2：正经的动规

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

思路3：分支定界

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        coins.sort(reverse=True)
        self.opt = amount + 1
        self.backTrack(coins, amount, 0, 0)
        return self.opt if self.opt <= amount else -1

    def backTrack(self, coins, amount, k, num):
        if amount == 0:
            if num < self.opt:
                self.opt = num
            return
        if k == len(coins)-1:
            if amount % coins[k] == 0:
                rst = num + amount / coins[k]
                if rst < self.opt:
                    self.opt = rst
            return
        for i in range(amount/coins[k], -1, -1):
            a = amount-i*coins[k]
            if num + i + a/coins[k+1] >= self.opt:
                return
            self.backTrack(coins, a, k+1, num + i)

好好努力！！！