自上而下方法的硬币找零问题比较

Question

我正在学习 LeetCode 322：零钱。

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation: 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]

两种解法唯一的区别在于，前者在for循环后的结果中加上了1（因为已经使用了一个硬币），而后者， 1 被添加到递归调用的参数中。

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

Answer 1

根据您使用 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

看到问题了吗？ memo 中没有正确的值。 memo[1] 应为 1，但代码将其设置为 4。同样，memo[3] 应为 2，但代码将其设置为 3。

要像您正在使用的那样使用 memo 数组，自下而上的工作会容易得多：从基本条件 (memo[0] = 0) 开始，然后计算值memo[1], memo[2], ... memo[amount] 基于先前计算的值。

Answer 2

OP 在这里：作为记录，这是修复 Tejas Narayan 指出的错误后的工作代码。

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。

自上而下方法的硬币找零问题比较

Coin change problem comparison of top-down approaches

python

algorithm

dynamic-programming