python - 无法弄清楚为什么我的代码不适用于特定情况(Leetcode 的硬币找零)

Question

以下是问题的链接:https://leetcode.com/problems/coin-change/

问题:

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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.

示例1:

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

Output: 3

Explanation: 11 = 5 + 5 + 1

示例2:

Input: coins = [2], amount = 3

Output: -1

我想出了以下代码，它通过了上面示例 1 中的测试用例，但没有通过示例 2 中的测试用例

这是我的代码，遵循解决方案描述的算法(附截图)

以下代码返回 0，而我期望返回 -1，因为结果等于 sys.maxsize

import sys
#declare global look up dictionary to store key (amount) and value (minimum number of coins)
lookup_dict = {}
#declare minimum number of coins and use the maximum number in python as place holder
minimum = sys.maxsize
def coinChange(coins,amount):
    result = coinChangeAux(coins, amount)
    return -1 if result==sys.maxsize else result

def coinChangeAux(coins, amount):
    #since we will modify minimum and lookup_dict, we put "global" in front of them
    global minimum,lookup_dict
    if amount in lookup_dict.keys():
        return lookup_dict[amount]
    if amount <= 0:
        lookup_dict[amount]=0
        return lookup_dict[amount]
    if not coins:
        return -1 
    for i in coins:
        if amount>=i:
            minimum = min(minimum,coinChange(coins,amount-i)+1)  
    lookup_dict[amount] = minimum
    return lookup_dict[amount]
coins=[2]
amount = 3
coinChange(coins,amount)

我尝试通过仅在下面的 coinChange 函数中返回结果来调试上面的代码，结果确实返回 9223372036854775807 ，它等于 sys.maxsize (所以我预计上面的 coinChange 函数应该返回 -1，因为结果等于 maxsize

import sys
#declare global look up dictionary to store key (amount) and value (minimum number of coins)
lookup_dict = {}
#declare minimum number of coins and use the maximum number in python as place holder
minimum = sys.maxsize
def coinChange(coins,amount):
    result = coinChangeAux(coins, amount)
    return result

def coinChangeAux(coins, amount):
    #since we will modify minimum and lookup_dict, we put "global" in front of them
    global minimum,lookup_dict
    if amount in lookup_dict.keys():
        return lookup_dict[amount]
    if amount <= 0:
        lookup_dict[amount]=0
        return lookup_dict[amount]
    if not coins:
        return -1 
    for i in coins:
        if amount>=i:
            minimum = min(minimum,coinChange(coins,amount-i)+1)  
    lookup_dict[amount] = minimum
    return lookup_dict[amount]
coins=[2]
amount = 3
coinChange(coins,amount)

Answer 1

当你递归时，你调用coinChange，这会将sys.maxsize变成-1。因此，minimum 的新值将为 −1 + 1 = 0。(sys.maxsize + 1 在 Python 中不会溢出，这是一件好事。)

仅调用包装函数coinChange一次，并递归调用coinChangeAux:

for i in coins:
    if amount >= i:
        minimum = min(minimum, coinChangeAux(coins, amount - i) + 1)