数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找使用印度货币面值获得n卢比的方案数
假设我们有有限数量的以下面值的硬币（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创建的一个新列表
- 对于i从0到(count[0]和n的最小值)，执行以下操作：
- A[i] := 1
- 对于i从1到3，执行以下操作：
- 对于j从0到count[i]，执行以下操作：
- 对于k从0到n + 1 - j *denom[i]，执行以下操作：
- B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
- 对于k从0到n + 1 - j *denom[i]，执行以下操作：
- 对于j从0到n，执行以下操作：
- A[j] := B[j]
- B[j] := 0
- 对于j从0到count[i]，执行以下操作：
- 返回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))输入
25, [7,3,2,2]
输出
9
更新于: 2021年10月23日
156 次浏览
广告