Leetcode 322. 零钱兑换

发表于
| 字数统计: 524 | 阅读时长 ≈ 2

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

1
2
输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

分析

如果要求出用1，2，5来凑11的最小个数，即求$f(11)$，而$f(11)$可以用$f(10)+1$，$f(9)+1$，$f(6)+1$中其中一个来表示，那么
$$f(11)=\min(f(10)+1， f(9)+1，f(6)+1)$$
同样的，为了计算$f(11)$，就需要知道$f(10),f(9),f(6)$的值。而
$$f(10)=\min(f(9)+1， f(8)+1，f(5)+1)$$
其中$f(9)$已经计算过了，可以用一个数组将其记录下来来减少计算量。

以此类推，最后可以得到
$$f(5)=f(2)=f(1)=1$$

新建一个dp数组，长度为amount + 1，第一个值为0，剩余的值为-1（表示无法搭配）

1
dp = [0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

之后开始对每一个amount进行判断，
$$dp[amount]=\min(dp[amount-coin]+1)$$

1
dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

dp[-1]就是我们需要的结果

对每个amount都需进行len(coins)次计算，时间复杂度为$O(n*k)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [-1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                # 因为dp[0] == 0，所以amount和coin相等的时候为dp[amount]==1
                if i - coin >= 0 and dp[i-coin] != -1:
                    # 这里需要初始化一下，否则在下面min比较的时候一直是-1
                    if dp[i] == -1: 
                        dp[i] = dp[i-coin] + 1
                    else:
                        dp[i] = min(dp[i], dp[i-coin] + 1)
        return dp[-1]

执行用时 : 2280 ms, 在Coin Change的Python3提交中击败了30.75% 的用户

内存消耗 : 13.1 MB, 在Coin Change的Python3提交中击败了96.51% 的用户

动态规划怎么这么慢？