程序查找用Python中给定的一组硬币进行更改所需的硬币数量

Z时代
2024-01-10
分类：综合

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

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

如果数量= 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)
      return dp[amount]
ob1 = Solution()print(ob1.coinChange([1,2,5],64))