递归记忆化解决方案"count changes"
Recursive memoization solutio to solve "count changes"
我正在尝试通过记忆解决 "Counting Change" 问题。
Consider the following problem: How many different ways can we make change of .00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a function to compute the number of ways to change any given amount of money using any set of currency denominations?
以及递归的直观解决方案。
使用n种硬币改变金额a的方法数等于
- 使用除第一种硬币以外的所有硬币来改变 a 的方法数,加上
- 使用所有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
记忆解决方案有什么问题?
在memoized版本中,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
我正在尝试通过记忆解决 "Counting Change" 问题。
Consider the following problem: How many different ways can we make change of .00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a function to compute the number of ways to change any given amount of money using any set of currency denominations?
以及递归的直观解决方案。
使用n种硬币改变金额a的方法数等于
- 使用除第一种硬币以外的所有硬币来改变 a 的方法数,加上
- 使用所有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
记忆解决方案有什么问题?
在memoized版本中,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