Проблема изменения монет Leetcode не дает правильного результата - PullRequest
Новая
       53

Проблема изменения монет Leetcode не дает правильного результата

0 голосов
/ 26 марта 2020

Я пишу коды для решения этой проблемы, ниже приведены мои коды, каким-то образом я вижу, что результат верен до конца для l oop, но после возврата функции он не выполняет правильный результат значение, см. ниже печать журнала, кто-нибудь может помочь с этим? Спасибо!

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

1 Ответ

0 голосов
/ 26 марта 2020

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
...