Python 中的找零问题

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

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

  • 如果 amount = 0，则返回 0
  • 如果 coins 数组的最小值 > amount，则返回 -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)
         #print(dp)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5], 11))

输入

[1,2,5]
11

输出

3

更新于： 2020-4-28

5K+ 次浏览

开启您的职业生涯

完成课程即可获得认证

开始
广告