<p>这里有两个解决零钱问题的程序。第一种是一种递归程序,可以得到所有的组合,第二种是使用动态规划。然而,当我在做第二个问题时,我遇到了麻烦。它应该比第一个快,但我的程序会永远运行。我很确定我使用的是动态编程,但我不知道它有什么问题?在</p>
<p>注:Total是将要更改的货币,units是具有不同值的列表,stored是存储步骤值的字典。在</p>
<p>第一个:</p>
<pre><code>def changeMoney(total, units):
if ( total == 0 ):
return [{}]
elif ( total < 0 ):
return []
else:
n = len(units)
ret = []
for i in range(0,n):
sols = changeMoney(total-units[i],units[i:n])
for sol in sols:
if ( units[i] in sol ):
sol[units[i]] += 1
else:
sol[units[i]] = 1
ret.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(sol)
return ret
print(dpChangeMoney(300,[100,50,20,10,5,2,1],{}))
</code></pre>
<p>第二:</p>
^{pr2}$