<p>这里有一种更快的方法:</p>
<pre><code>def dpChangeMoney(total, units, stored, min_ix=0):
if total < 0:
return []
if total == 0:
return [{}]
if min_ix == len(units):
return []
key = (total, min_ix)
if key in stored:
return stored[key]
sol_list = []
u = units[min_ix]
for c in range(total // u + 1):
sols = dpChangeMoney(total - c*u, units, stored, min_ix + 1)
for sol in sols:
if c > 0:
sol2 = sol.copy()
sol2[u] = c
else:
sol2 = sol
sol_list.append(sol2)
stored[key] = sol_list
return sol_list
</code></pre>
<p>如果按如下方式调用,它将打印指定案例的解决方案数:</p>
^{pr2}$
<p>结果是:</p>
<pre><code>466800
</code></pre>
<p>在我的系统上,这只花了不到一秒钟的时间。(当然,您可以打印出实际的解决方案,但有很多!)在</p>
<p>要查看总共<code>10</code>的实际解决方案:</p>
<pre><code>print(dpChangeMoney(10, [100,50,20,10,5,2,1], {}))
</code></pre>
<p>结果是:</p>
<pre><code>[{1: 10}, {1: 8, 2: 1}, {1: 6, 2: 2}, {1: 4, 2: 3}, {1: 2, 2: 4}, {2: 5}, {1: 5, 5: 1}, {1: 3, 2: 1, 5: 1}, {1: 1, 2: 2, 5: 1}, {5: 2}, {10: 1}]
</code></pre>