資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：計算使用不同硬幣組合可以得到的不同金額數
假設我們有一個名為coins的數值列表和另一個名為quantities的相同長度的列表。第i枚硬幣的值為coins[i]，我們目前有quantities[i]個第i枚硬幣。我們需要找到使用這些硬幣的非空組合可以得到的不同金額數。
例如，如果輸入為coins = [1, 2, 5]，quantities = [1, 2, 1]，則輸出為10，因為我們可以得到以下不同的金額：[1] = 1，[2] = 2，[1,2] = 3，[2,2] = 4，[5] = 5，[1,5] = 6，[2,5] = 7，[1,2,5] = 8，[2,2,5] = 9，[1,2,2,5] = 10。
為了解決這個問題，我們將遵循以下步驟
定義一個函式rec()。它將接收i和res作為引數。
if i is same as size of coins , then return for k in range 0 to quantities[i] + 1, do cur := res + k * coins[i] insert cur into fres rec(i + 1, cur) From the main method, do the following: fres := a new set rec(0, 0) return size of fres - 1
示例
class Solution: def solve(self, coins, quantities): def rec(i, res): if i == len(coins): return for k in range(0, quantities[i] + 1): cur = res + k * coins[i] fres.add(cur) rec(i + 1, cur) fres = set() rec(0, 0) return len(fres) - 1 ob = Solution() coins = [1, 2, 5] quantities = [1, 2, 1] print(ob.solve(coins, quantities))
輸入
[1, 2, 5], [1, 2, 1]
輸出
10
更新於：2020年11月10日
521 次瀏覽
廣告