改变硬币的方法数

Question

我正在做这道题https://leetcode.com/problems/coin-change-2/。给定数量和面额，我需要找到多种更改硬币的方法。我想出了一个解决方案来尝试每种可能的金额面额，如果以前见过，就缓存它。class Solution(object):    def change(self, amount, coins):        """        :type amount: int        :type coins: List[int]        :rtype: int        """        dp = [[-1]*len(coins)]*(amount+1)        def changeHelper(amount, coins, index):            if amount == 0:                return 1            if index<0:                return 0            if dp[amount][index]!=-1:                return dp[amount][index]            total_ways = 0            if amount>=coins[index]:                total_ways = changeHelper(amount-coins[index], coins, index)            total_ways += changeHelper(amount, coins, index-1)            dp[amount][index] = total_ways            return dp[amount][index]        return changeHelper(amount, coins, len(coins)-1)我得到了错误的答案，并且花了几个小时来找出错误。Test case500[1,2,5]expected answer 12701my output 301

Answer 1

您的代码很好，问题在dp列表中。当您[[-1]*len(coins)]*(amount+1)在示例中执行此操作时，首先会创建一个列表，[-1, -1, -1]然后将其复制（通过引用）501次。当您更改任何列表中的任何项目时，所有其他列表也会更新，这将导致不正确的结果。

要解决此问题，请使用列表理解创建列表：

dp = [[-1 for _ in range(len(coins))] for _ in range(amount+2)]

或利用dictlookupO(1)在 Python 中的事实并使用dictfor memoization 以避免将来出现此类错误，例如：

dp = {}

def changeHelper(amount, coins, index):

    if amount == 0:

        return 1

    if index<0:

        return 0

    if (amount, index) in dp:

        return dp[(amount, index)]

    total_ways = 0

    if amount>=coins[index]:

        total_ways = changeHelper(amount-coins[index], coins, index)

    total_ways += changeHelper(amount, coins, index-1)

    dp[(amount, index)] = total_ways

    return dp[(amount, index)]

编辑：

这是为什么会发生的更多解释

>>> dp = [[-1] * 3] * 4

>>> dp

[[-1, -1, -1], [-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]

>>> dp[0][0] = 5

>>> dp

[[5, -1, -1], [5, -1, -1], [5, -1, -1], [5, -1, -1]]

可以这样想，内部语句创建：

tmp = [-1, -1, -1]

然后是外面的：

dp = [tmp, tmp, tmp, tmp]

Answer 2

这是您需要的 DP。

def change(amount, coins):

        dp = [0] * (amount + 1)

        dp[0] = 1

        for x in range(amount + 1):

            for c in coins:

                if c > x: continue

                dp[x] += dp[x - c]

        return dp[amount]