程序查找在Python中进行更改所需的硬币数量

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

假设我们有不同面额的硬币(1,5,10,25)和总金额。我们必须定义一个函数来计算组成该数量所需的最少数量的硬币。因此，如果输入为64，则输出为7。这是使用25 + 25 + 10 + 1 + 1 + 1 + 1 = 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, amount):
          coins = [1,5,10,25]
          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(64))

    输入项

    64

    输出结果

    7

    以上是 程序查找在Python中进行更改所需的硬币数量 的全部内容， 来源链接： utcz.com/z/343630.html

    回到顶部