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]
Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.
输出
9
广告