0

我是 CS 的新手,我只是尝试使用递归解决变更问题,在另一个问题Recursive change-making algorithm

def change(total, coins):
    def coin_change(remain, position, changes=None):
        changes=[] if changes is None else changes
        if remain == 0:
            return len(changes), changes
        elif remain < 0 or position == -1:
            return float('inf'), changes
        else:
            strategy1 = coin_change(remain, position-1, changes)
            strategy2 = coin_change(remain-coins[position], position, 
                                    changes+[coins[position]])
        if strategy1[0] >= strategy2[0]:
            return strategy2
        else:
            return strategy1
    return coin_change(total, len(coins)-1, changes=None)

当给定较小(49, [1,5,12,24])的输入((1000, [1,5,12,24])例如

File "********\coin_change.py", line 56, in testperformance
function1(1480, [1, 7, 24, 42])

虽然我已经通过使用一些动态编程技术解决了这个问题,但我真的很好奇我的初始代码有什么问题。是堆栈溢出问题吗?它是如何发生的?希望一些明确的解释或参考资料。

4

0 回答 0