用m币兑换n美元
回答此问题可获得 20 贡献值，回答如果被采纳可获得 50 分。
<p>我正在尝试解决以下问题：</p>
<blockquote>
<p>Given a number of dollars, n, and a list of dollar values for m
distinct coins, find and print the number of different ways you can
make change for n dollars if each coin is available in an infinite
quantity.</p>
</blockquote>
<p>完整的问题陈述是<a href="https://www.hackerrank.com/challenges/ctci-coin-change/problem" rel="nofollow noreferrer">here</a></p>
<p>在介绍我的解决方案之前，我应该说，我知道动态编程可能是解决这个问题的最佳方法。我提出的解决方案不使用动态编程，而且我知道它远远不是最有效的解决方案。不过，据我所知是正确的。在</p>
<p>问题是我的解决方案低估了改变的方法。例如，给定<code>n = 75</code>和<code>{25 10 11 29 49 31 33 39 12 36 40 22 21 16 37 8 18 4 27 17 26 32 6 38 2 30 34}</code>作为硬币值，解决方案在应返回16694时返回182。不过，它似乎适用于较小的测试用例。在</p>
<pre><code>def make_change(coins, n):
solns = 0
num_coins = len(coins)
for i in range(num_coins):
solns = solns + make_change_rec(coins, n-coins[0], coins[0])
# We've found all solutions involving coin. Remove it
# from consideration
coins.pop(0)
return solns
def make_change_rec(coins, n, parent):
# If n == 0 we've found a solution
if n == 0:
return 1
solns = 0
# For each coin
for coin in coins:
# If coin > n, can't make change using coin
if coin > n or coin < parent: # coin < parent rule ensures we don't count same solution twice
continue
# Use the coin to make change
solns = solns + make_change_rec(coins, n-coin, coin)
return solns
</code></pre>
<p>有人能帮我理解我做错了什么吗？我用的是python3。在</p>
请先 登录 后评论
针对此问题: 更多的回答
- 89 关注
- 1 收藏，216 浏览
- 网友 提问于 2天前
相关Python问题
- Python中两个字典的交集 9 回答
- python中两个字符串上的异或操作数？ 3 回答
- Python中两个字符串中的类似句子 2 回答
- Python中两个字符串之间的Hamming距离 5 回答
- python中两个字符串之间的匹配模式 7 回答
- python中两个字符串之间的按位或 8 回答
- python中两个字符串之间的数据（字节）切片 3 回答
- python中两个字符串之间的模式 1 回答
- python中两个字符串作为子字符串的区别 7 回答
- Python中两个字符串元组的比较 6 回答
- Python中两个字符串列表中的公共字符串 3 回答
- python中两个字符串的Anagram测试 6 回答
- Python中两个字符串的正则匹配 9 回答
- python中两个字符串的笛卡尔乘积 4 回答
- Python中两个字符串相似性的比较 5 回答
- python中两个字符串语义相似度的求法 9 回答
- Python中两个字符置换成固定长度的字符串，每个字符的数目相等 1 回答
- Python中两个对数方程之间的插值和平滑数据 9 回答
- Python中两个对象之间的And/Or运算符 6 回答
- python中两个嵌套字典中相似键的和值 1 回答
