Python中的硬币更改

假设我们有不同面额的硬币和总金额。我们必须定义一个函数来计算组成该数量所需的最少数量的硬币。如果硬币的任何组合都无法容纳该金额，请返回-1。因此，如果输入为[1,2,5]，且数量为11，则输出为3。这是使用5 + 5 + 1 = 11形成的。

为了解决这个问题，我们将遵循以下步骤-

• 如果数量= 0，则返回0

• 如果最小的硬币数组>数量，则返回-1

• 定义一个称为dp的数组，大小为+1，并用-1填充

• 对于我在范围硬币阵列

• 如果dp [j – 1] = -1，则跳过下一部分，进行下一次迭代

• 否则，如果dp [j] = -1，则dp [j]：= dp [j-i] + 1

• 否则dp [j]：= dp [j]和dp [j – i]的最小值+ 1

• 如果i> dp的长度– 1，则跳过下一部分，进行下一次迭代

• dp [i]：= 1

• 对于范围i +1中的j等于

• 返回dp [金额]

示例

让我们看下面的实现以更好地理解-

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)
         #print(dp)
      return dp[amount]
ob1 = Solution()print(ob1.coinChange([1,2,5], 11))

输入项

[1,2,5]
11

输出结果

3