python - leetcode 硬币找零问题没有给出正确的结果

Question

我正在编写代码来解决这个问题，下面是我的代码，不知何故我看到结果是正确的，直到 for 循环结束，但是函数返回后它没有执行正确的结果值，见下面的日志打印，有人可以帮忙吗？谢谢！

https://leetcode.com/problems/coin-change/

"""
sort the coins to start with coin that has largest value;
then loop through possible number of that coins we could put, 
and use dfs to go through other possible coin types
"""
def coinChange(self, coins, amount):
    # write your code here
    coins.sort()
    coins=coins[::-1]

    n=len(coins)
    res=100000000000000



    def getcom(i, coins, amount,count, res):

        if amount==0:
            res=min(res, count)
            print("res: ", res)


        if i==n:
            return

        coin=coins[i]
        print("coin:", coins[i])
        k=amount//coin
        print("k:", k)
        for j in range(k, -1, -1):
            if count+j>res:
                break
            getcom(i+1, coins, amount-k*coin, count+k, res)

    getcom(0,coins, amount, 0,res)        
    return res

---

testcase:Input: coins = [1, 2, 5], amount = 11
should Output: 3 

解释：11 = 5 + 5 + 1

my stdout
coin: 5
k: 2
coin: 2
k: 0
coin: 1
k: 1
res:  3
res:  3
coin: 2
k: 0
coin: 1
k: 1
res:  3
res:  3
coin: 2
k: 0
coin: 1
k: 1
res:  3
res:  3

----------
my output: 100000000000000

标签： pythondepth-first-searchgreedypruning

Answer 1

res在方法调用中被修改但从未返回。

递归计算的结果不会传回调用堆栈。您需要添加一些return语句。

"""
sort the coins to start with coin that has largest value;
then loop through possible number of that coins we could put, 
and use dfs to go through other possible coin types
"""
def coinChange(coins, amount):
    # write your code here
    coins.sort()
    coins=coins[::-1]

    n=len(coins)
    res=100000000000000



    def getcom(i, coins, amount,count, res):
        #nonlocal res
        if amount==0:
            res=min(res, count)
            print("res: ", res)


        if i==n:
            return res

        coin=coins[i]
        print("coin:", coins[i])
        k=amount//coin
        print("k:", k)
        for j in range(k, -1, -1):
            if count+j>res:
                break
            return getcom(i+1, coins, amount-k*coin, count+k, res)

    res = getcom(0,coins, amount, 0,res)
    return res

print(coinChange([1,2,5], 11))

输出：

coin: 5
k: 2
coin: 2
k: 0
coin: 1
k: 1
res:  3
3