<p>谢谢<a href="https://stackoverflow.com/users/2864740/user2864740">@user2864740</a>
和<a href="https://stackoverflow.com/users/1509433/dannyadam">@dannyadam</a></p>
<p>我将把我的最终代码留给以后看这篇文章的人</p>
<pre class="lang-py prettyprint-override"><code>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)
</code></pre>
<p>在实现了这个示例之后,我开始认为这是一个糟糕的记忆玩具示例。我可以编写一个贪婪算法,在每一步选择价值最大的硬币。e、 g.从42c中减去25c,从17c中减去10c,以此类推,同时递增计数器</p>