链接到问题:https://leetcode.com/problems/coin-change/
我的代码无法从LeetCode传递一些测试用例:
def coinChange(coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
coins.sort()
#init the dp list
dp = [0]+[float('inf')]*amount
for i in coins:
for j in range(i,amount+1):
dp[j] = min(dp[j],int(j/i)+dp[j%i])
if dp[-1]==float('inf'):
return -1
else:
return dp[-1]
#test cases1,the result should be 3
coins = [1, 2, 5]
amount = 11
print(coinChange(coins,amount))
#test cases2,the result should be 20
coins = [186,419,83,408]
amount = 6249
print(coinChange(coins,amount))
对于第二个测试用例,它应该返回20,但现在是-1。我不知道为什么我的代码适用于第一个测试用例,而不是第二个测试用例。
谢谢
发布于 2017-01-05 00:35:45
我不知道你想在dp[j] = min(dp[j],int(j/i)+dp[j%i])
中做什么,但应该是dp[j] = min(dp[j],1+dp[j-i])
。原因是,您可以添加此硬币与金额j-i
,以获得金额j
与多一个硬币(这个硬币)。
https://stackoverflow.com/questions/41479112
复制相似问题