Количество способов поменять монету

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)]

или используйте тот факт, что поиск dict равен O(1) в Python, и используйте 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]

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]