Python程序：查找凑零钱所需的硬币数量

假设我们有不同面额的硬币和一个总金额。我们需要定义一个函数来计算凑成该金额所需的最少硬币数量。当该金额无法由任何硬币组合凑成时，返回 -1。所以如果输入是 [1, 2, 5]，金额是 64，输出是 14。这是由 12*5 + 2 + 2 = 64 组成。

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

• 如果金额 = 0，则返回 0
• 如果硬币数组的最小值 > 金额，则返回 -1
• 定义一个名为 dp 的数组，大小为 amount + 1，并将其全部填充为 -1
• 对于 coins 数组中的每个 i
  • 如果 i > dp 长度 - 1，则跳过下一部分，进行下一次迭代
  • dp[i] := 1
  • 对于 j 从 i + 1 到 amount
    • 如果 dp[j – 1] = -1，则跳过下一部分，进行下一次迭代
    • 否则，如果 dp[j] = -1，则 dp[j] := dp[j - i] + 1
    • 否则 dp[j] := dp[j] 和 dp[j – i] + 1 的最小值
• 返回 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

Arnab Chakraborty

更新于: 2020-10-19

198 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习