私のコードが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)) 

は、第2のテストケースのために20を返す必要がありますが、今、それはだ-1。 私のコードが最初のテストケースでは動作するが、2番目のテストケースではなぜ動作しないのかわかりません。
ありがとう

Answer 1

dp[j] = min(dp[j],int(j/i)+dp[j%i])で何をしようとしているのかわかりませんが、dp[j] = min(dp[j],1+dp[j-i])である必要があります。その理由は、このコインに金額j-iを加えて、もう一つのコイン（このコイン）で金額jを得ることができるからです。