为什么我的代码不能通过LeetCode 322 Coin Change的测试用例？

Question

问题的链接：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。我不知道为什么我的代码可以在第一个测试用例上工作，但不能在第二个测试用例上工作<谢谢

Answer 1

我不确定你想在dp[j]=min（dp[j]，int（j/I）dp[j%I]）中做什么，但它应该是dp[j]=min（dp[j]，1 dp[j-I]）。原因是，您可以将此硬币添加到amountj-i中，再添加一枚硬币（此硬币）即可获得amountj。