python - 改变硬币的方法数

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

标签： pythondynamic-programming

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]