更换硬币的方式数目

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 case
500
[1,2,5]
expected answer 12701
my output 301

Answer 1

这是您需要的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]

Answer 2

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

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

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

或利用Python中的dict查找为O(1)的事实，并使用dict进行记录以避免将来发生此类错误，例如：

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]