Jianbo Dai's

mq063.零钱兑换

 
  • Jan 20, 2021

题目链接

这题和完全背包问题相似，不同处在于这题要求容积要恰好填满，但是完全背包问题只要求“不超过”，并且这题要求的是方案数，而完全背包问题要求一个小于容积的最大值。首先尝试用填满二维表格的方法，我们设f[i][j]为考虑前i种硬币，凑出金额为j的最少数目。考虑第i种硬币，我们可以不拿，或者拿i…k个，直到超出总金额。f[i][j] = min(f[i-1][j], f[i-1][j-c]+1, f[i-1][j-2c]+2, …, f[i-1][j-kc]+k)，又因为其中包含了大量冗余的运算，例如: f[i][j-c] = min(f[i-1][j], f[i-1][j-2c]+1, …, f[i-1][j-kc]+(k-1))，将两者合并可以得到f[i][j] = min(f[i-1][j], f[i][j-c]+1)。我们将该思路用代码实现出来，如1所示，其中需要注意的是当j小于当前考虑的硬币都面值的时候，我们要直接将上一行的数据复制下来。这样直到计算出最右下角的元素即为最小需要硬币的数量。这个方法的时间复杂度是O（NM），空间复杂度是O（NM），其中N为零钱种类，M为金额。

考虑到f[i][j]只和上一层的一个状态f[i-1][j]以及这一层的一个状态f[i][j-c]+1有关，我们可以将状态优化为一维数组。如2所示，此时我们将空间复杂降低为了O（M）。因为金额从小到大枚举，所以计算j时，j-c的状态已经计算好了，可以直接替换。这里恰好是与0-1背包问题相反的。

python:

class Solution:
    def coinChange1(self, coins: List[int], amount: int) -> int:
        if amount < 0:
            return -1

        cnum = len(coins)
        dp = [[amount + 1]*(amount+1) for _ in range(cnum+1)]

        for i in range(cnum+1):
            dp[i][0] = 0
        
        for i in range(1, cnum+1):
            for j in range(1, amount+1):
                if j < coins[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]+1)
        return -1 if dp[-1][-1] == (amount+1) else dp[-1][-1]
				
    def coinChange2(self, coins, amount):
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        for e in coins:
            for j in range(e, amount+1):
                dp[j] = min(dp[j], dp[j-e]+1)
        return -1 if dp[-1] == (amount+1) else dp[-1]
Search