硬币兑换问题自上而下方法的比较

Question

我正在研究Leetcode322：硬币兑换。

您将获得一个整数数组，表示不同面额的硬币，以及一个整数金额，表示总金额。

返回您需要的最少数量的硬币，以弥补该金额。如果这些硬币的任何组合都无法弥补这一数额，则返回-1。

你可以假设每种硬币的数量是无限的。

例子：

输入：硬币=[1,2,5]，金额=11

输出： 3

说明：11 = 5 5 1

我选择自上而下的方法，在每次迭代中，我选择一个面额不大于剩余金额的硬币。听起来很容易，对吧？

以下代码通过所有测试用例。

import sys
import functools

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @functools.cache   
        def _loop(remaining: int) -> int:
            if remaining == 0:
                return 0
            y = sys.maxsize
            for coin in filter(lambda x: x <= remaining, coins):
                y = min(y, _loop(remaining - coin))

            return (y + 1) if y < sys.maxsize else y
        
        num_coins = _loop(amount)
        return num_coins if num_coins < sys.maxsize else -1 

但这一个没有。

import sys
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        num_coins = self._loop(coins, amount, 0, {})
        return num_coins if num_coins < sys.maxsize else -1
    
    def _loop(self, coins: Sequence[int], remaining: int, count: int, memo: MutableMapping[int, int]) -> int:
        if remaining == 0:
            return count
        if remaining not in memo:
            y = sys.maxsize
            for coin in filter(lambda x: x <= remaining, coins):
                y = min(y, self._loop(coins, remaining - coin, count + 1, memo))
            memo[remaining] = y

        return memo[remaining]

这两种解决方案的唯一区别是，在前者中，1被添加到for循环之后的结果中（因为使用了一枚硬币），在后者中，1被添加到递归调用的参数。

第二个解决方案中我没有看到的错误是什么？

Answer 1

这里的操作：为了记录在案，这是修复泰哈斯·纳拉扬指出的错误后的工作代码。

import sys
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        num_coins = self._loop(coins, amount, 0, {})
        return num_coins if num_coins < sys.maxsize else -1
    
    def _loop(self, coins: Sequence[int], remaining: int, count: int, memo: MutableMapping[int, int]) -> int:
        if remaining == 0:
            return count
        if remaining not in memo:
            y = sys.maxsize
            for coin in filter(lambda x: x <= remaining, coins):
                y = min(y, self._loop(coins, remaining - coin, 1, memo))

            memo[remaining] = (y + count) if y < sys.maxsize else y

        return memo[remaining]

对于每个递归调用，修复被重置为count到1。

Answer 2

根据您使用memo的方式，memo[x]意味着包含总计x美分所需的最小硬币数量。然而，事实并非如此。

让我们看看递归堆栈：

remaining = 4, count = 0, y = maxsize, take coin 1:
    remaining = 3, count = 1, y = maxsize, take coin 1:
        remaining = 2, count = 2, y = maxsize, take coin 1:
            remaining = 1, count = 3, y = maxsize, take coin 1:
                remaining = 0, count = 4, RETURN 4
            y = 4, memo[1] = 4, RETURN 4
        remaining = 2, count = 2, y = 4, take coin 2:
            remaining = 0, count = 3, RETURN 3
        y = 3, memo[2] = 3, RETURN 3
    remaining = 3, count = 1, y = 3, take coin 2:
        remaining = 1, count = 2, memo[1] exists, RETURN 4
    y = 3, memo[3] = 3, RETURN 3
remaining = 4, count = 0, y = 3, take coin 2:
    remaining = 2, count = 1, memo[2] exists, RETURN 3
y = 3, memo[4] = 3, RETURN 3

看到问题了吗<代码>备忘录中的值不正确<代码>备忘录[1]应为1，但代码将其设置为4。类似地，memo[3]应该是2，但代码将其设置为3。

要像您正在使用的那样使用memo数组，从下到上工作会容易得多：从一个基本条件（memo[0]=0）开始，计算memo[1]、memo[2]、。。。备注[金额]基于先前计算的值。