用 Python 编写程序，查找进行更改所需的硬币数量

pythonserver side programmingprogramming更新于 2026/2/1 14:36:17

假设我们有不同面额的硬币(1、5、10、25)和总金额。我们必须定义一个函数来计算凑足该金额所需的最少硬币数量。因此，如果输入为 64，则输出为 7。这由 25 + 25 + 10 + 1 + 1 + 1 + 1 = 64 组成。

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

如果 amount = 0，则返回 0
如果硬币数组的最小值 > amount，则返回 -1
定义一个名为 dp 的数组，大小为 amount + 1，并用 -1 填充它
for i in range coins array
- 如果 i > dp 的长度 – 1，则跳过下一部分，进行下一次迭代
- dp[i] := 1
- for j in range i + 1 to 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, 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))