Pythonで与えられたコインのセットで変更を加えるために必要なコインの数を見つけるためのプログラム

異なる金種のコインと合計金額があるとします。その量を構成するために必要なコインの最小数を計算するために、1つの関数を定義する必要があります。コインの組み合わせでその金額に対応できない場合は、-1を返します。したがって、入力が[1,2,5]で、金額が64の場合、出力は14になります。これは12 * 5 + 2 + 2=64を使用して形成されます。

これを解決するには、次の手順に従います-

• 金額=0の場合、0を返します
• コイン配列の最小量>の場合、-1を返します
• サイズが+1のdpという1つの配列を定義し、これに-1を入力します
• for i in range coins array
  • i> dp – 1の長さの場合、次の部分をスキップして、次の反復に進みます
  • dp [i]：=1
  • 範囲i+1から量のjの場合
    • dp [j – 1] =-1の場合、次の部分をスキップして、次の反復に進みます
    • それ以外の場合、dp [j] =-1の場合、dp [j]：=dp [j --i] + 1
    • それ以外の場合、dp [j]：=最小のdp[j]およびdp[j – i] + 1
• return dp [amount]

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def coinChange(self, coins, amount):
      if amount == 0 :
         return 0
      if min(coins) > amount:
         return -1
      dp = [-1 for i in range(0, amount + 1)]
      for i in coins:
         if i > len(dp) - 1:
            continue
         dp[i] = 1
         for j in range(i + 1, amount + 1):
            if dp[j - i] == -1:
               continue
            elif dp[j] == -1:
               dp[j] = dp[j - i] + 1
            else:
               dp[j] = min(dp[j], dp[j - i] + 1)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5],64))

入力

[1,2,5], 64

出力

14