資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告