通过记忆实现零钱的最小硬币数量

Question

我正在练习动态编程的概念(递归不是我的强项(。我想知道如何改进我的代码，这样我就可以避免堆栈溢出。

任何帮助，谢谢！

def coinFlipping(n):
"""
For n amount of change, return the minimal amount of currency in coins.
Top-Down Approach (Memoization): Memo dictionary stores already solved
subproblems to reuse and avoid recomputing. It's essentially recursion 
but optimized to avoid recomputing results. 
"""
COINS = {
"penny": 0.01,
"nickel": 0.05,
"dime": 0.10,
"quarter": 0.25,
"dollar": 1.00
}
memo = {}
def __coinFlipping(n):
if n not in memo:
# Base case (if n is equal to 0.01, 0.05, 0.10, 0.25..)
if n in COINS.values():
memo[n] = 1
else:
results = []
coins = (coin for coin in COINS.values() if coin < n)
for coin in coins:
results.append(__coinFlipping(n - coin))
memo[n] = 1 + min(results)
else:
return memo[n]         
__coinFlipping(n)
print(memo[n])
coinFlipping(10)

我获得了以下错误：

File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 45, in __coinFlipping
results.append(__coinFlipping(n - coin))
File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 45, in __coinFlipping
results.append(__coinFlipping(n - coin))
File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 45, in __coinFlipping
results.append(__coinFlipping(n - coin))
[Previous line repeated 993 more times]
File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 44, in __coinFlipping
for coin in coins:
File "/mnt/d/programs/algorithms/dynamicProgramming.py", line 43, in <genexpr>
coins = (coin for coin in COINS.values() if coin < n)
RecursionError: maximum recursion depth exceeded in comparison

Answer 1

谢谢@user2864740和@dannyadam

我将把我的最终代码留给任何看完这篇文章的人。

def coinFlipping(n):
"""
For n amount of cents, return the minimal amount of currency in coins.
Top-Down Approach (Memoization): Memo dictionary stores already solved
subproblems to reuse and avoid recomputing. It's essentially recursion 
but optimized to avoid recomputing results. 
"""
COINS = {
"dollar": 100,
"quarter": 25,
"dime": 10,
"nickel": 5,
"penny": 1
}
memo = {}
def __coinFlipping(change):
if change not in memo:
# Base case (if n is equal to 0.01, 0.05, 0.10, 0.25..)
if change in COINS.values():
memo[change] = 1
else:
results = []
coins = [coin for coin in COINS.values() if coin < change]
for coin in coins:
results.append(__coinFlipping(change - coin))
memo[change] = 1 + min(results)
return memo[change]         

__coinFlipping(n)
print(memo[n])
coinFlipping(42)

在实现了这个示例之后，我开始认为它是一个糟糕的记忆玩具示例。我本可以写一个贪婪的算法，在每一步中选择价值最大的硬币。例如从42c减去25c和从17c减去10c等等，同时递增计数器。

Answer 2

user2864740很到位。更改为整数，代码就会运行。