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