Leetcode 518 Coin Change 2

发表于 |

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

注意: 你可以假设

  1. 0 <= amount (总金额) <= 5000
  2. 1 <= coin (硬币面额) <= 5000
  3. 硬币种类不超过500种
  4. 结果符合32位符号整数

示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:
输入: amount = 10, coins = [10]
输出: 1

分析：

  1. 回溯过不了，因为最小的coin会很小，当amount达到5000的时候递归爆炸
  2. 只能是用dp[i]记录组成i元钱有多少种方法，最后返回dp[amount]即可
  3. 这种思想还挺常见的，我要不是以前做过好几道这样的题目可能也想不到，所以你如果也没想到不要担心，多做之后自然就能想到了
  4. 不过这里有一个点和我以前见到用这个方法的题目是不太一样的，那就是这里是对dp进行顺序遍历，以往都是需要逆序遍历的，就为了防止重复利用数字，但这里恰恰是要重复使用！

思路：

  1. 建立dp数组，初始化dp[0] = 1
  2. dp[i] += dp[i-coins[j]] for j in range(len(coins)
  3. 顺序遍历数组，以示例1中数据为例：
    1. dp = [1,0,0,0,0,0] 初始情况
    2. dp = [1,1,1,1,1,1] 对于coins[0]=1
    3. dp = [1,1,2,2,3,3] 对于coins[1]=2
    4. dp = [1,1,2,2,3,4] 对于coins[2]=5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        :这道题的数据有丶搞的，看样子回溯可能怎样优化都过不了了，只能是dp了
        """
        if not amount: return 1
        if not coins: return 0
        coins.sort()
        dp = [0] * (amount+1)
        dp[0] = 1
        for c in coins:
            for i in range(1,len(dp)):
                if i - c >= 0:
                    dp[i] += dp[i-c]
        # print dp
        return dp[-1]


27 / 27 test cases passed.
difficulty: medium
Runtime: 144 ms,beats 79%