用 Python 编写程序，找出使用印度面额获得 n Rs 的方法数

pythonserver side programmingprogramming更新于 2026/1/31 15:08:17

假设我们有有限面额的硬币(₹1、₹2、₹5 和 ₹10)。我们必须找出有多少种方法可以将它们加起来达到 ₹n 的总数?我们有一个大小为 4 的数组 count，其中 count[0] 表示 ₹1 的硬币，count[1] 表示 ₹2 的硬币，依此类推。

因此，如果输入为 n = 25 count = [7,3,2,2]，则输出为 9。

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

denom := [1,2,5,10]
A := 大小为 (n + 1) 的数组并用 0 填充
B := 来自 A 的新列表
对于范围为 0 到 (count[0] 和 n 的最小值) 的 i，执行
- A[i] := 1
对于范围为 1 到 3 的 i，执行
- 对于范围在 0 到 count[i] 内的 j，执行
  - 对于范围在 0 到 n + 1 - j *denom[i] 内的 k，执行
    - B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
- 对于范围在 0 到 n 内的 j，执行
  - A[j] := B[j]
  - B[j] := 0
返回 A[n]

示例

让我们看看下面的实现以便更好地理解 −

denom = [1,2,5,10]
def solve(n, count):
   A = [0] * (n + 1)
   B = list(A)
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j *denom[i]):
            B[k + j * denom[i]] += A[k]
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 25
count = [7,3,2,2]
print(solve(n, count))