递归记忆解决方案解决"count changes"

Question

我正试图通过记忆来解决"计算变化"的问题。

考虑以下问题：给定半美元、25美分、1美分、5美分和1美分，我们可以用多少种不同的方式兑换1.00美元？更普遍地说，我们能写一个函数来计算使用任何一组货币面额来改变任何给定金额的方法的数量吗？

以及带有递归的直观解决方案。

使用n种硬币更改金额a的方法数等于

1. 使用除第一种硬币外的所有硬币更改的方法的数量，加上
2. 使用所有n种硬币改变较小金额a-d的方法的数量，其中d是第一种硬币的面额

---

#+BEGIN_SRC python :results output
# cache = {} # add cache 
def count_change(a, kinds=(50, 25, 10, 5, 1)):
"""Return the number of ways to change amount a using coin kinds."""
if a == 0:
return 1
if a < 0 or len(kinds) == 0:
return 0
d = kinds[0]　# d for digit
return count_change(a, kinds[1:]) + count_change(a - d, kinds) 
print(count_change(100))
#+END_SRC
#+RESULTS:
: 292

我尽量利用记忆，

Signature: count_change(a, kinds=(50, 25, 10, 5, 1))
Source:   
def count_change(a, kinds=(50, 25, 10, 5, 1)):
"""Return the number of ways to change amount a using coin kinds."""
if a == 0:
return 1
if a < 0 or len(kinds) == 0:
return 0
d = kinds[0]
cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
return cache[a]

它适用于像这样的小数字

In [17]: count_change(120)
Out[17]: 494

研究大数字

In [18]: count_change(11000)                        
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-18-52ba30c71509> in <module>
----> 1 count_change(11000)
/tmp/ipython_edit_h0rppahk/ipython_edit_uxh2u429.py in count_change(a, kinds)
9         return 0
10     d = kinds[0]
---> 11     cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
12     return cache[a]
... last 1 frames repeated, from the frame below ...
/tmp/ipython_edit_h0rppahk/ipython_edit_uxh2u429.py in count_change(a, kinds)
9         return 0
10     d = kinds[0]
---> 11     cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
12     return cache[a]
RecursionError: maximum recursion depth exceeded in comparison

记忆解决方案有什么问题？

Answer 1

在记忆版本中，count_change函数必须考虑您在进行递归调用时可以使用的最高硬币索引，这样您就可以使用已经计算好的值。。。

def count_change(n, k, kinds):
if n < 0:
return 0
if (n, k) in cache:
return cache[n,k]
if k == 0:
v = 1
else:
v = count_change(n-kinds[k], k, kinds) + count_change(n, k-1, kinds)
cache[n,k] = v
return v

你可以试试：

cache = {}
count_change(120,4, [1, 5, 10, 25, 50])

给出494

而：

cache = {}
count_change(11000,4, [1, 5, 10, 25, 50])

输出：9930221951