改变硬币的方法数

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列表中。当您[[-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):&nbsp; &nbsp; if amount == 0:&nbsp; &nbsp; &nbsp; &nbsp; return 1&nbsp; &nbsp; if index<0:&nbsp; &nbsp; &nbsp; &nbsp; return 0&nbsp; &nbsp; if (amount, index) in dp:&nbsp; &nbsp; &nbsp; &nbsp; return dp[(amount, index)]&nbsp; &nbsp; total_ways = 0&nbsp; &nbsp; if amount>=coins[index]:&nbsp; &nbsp; &nbsp; &nbsp; total_ways = changeHelper(amount-coins[index], coins, index)&nbsp; &nbsp; total_ways += changeHelper(amount, coins, index-1)&nbsp; &nbsp; dp[(amount, index)] = total_ways&nbsp; &nbsp; 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):&nbsp; &nbsp; &nbsp; &nbsp; dp = [0] * (amount + 1)&nbsp; &nbsp; &nbsp; &nbsp; dp[0] = 1&nbsp; &nbsp; &nbsp; &nbsp; for x in range(amount + 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for c in coins:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if c > x: continue&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dp[x] += dp[x - c]&nbsp; &nbsp; &nbsp; &nbsp; return dp[amount]