Giả sử chúng ta có một danh sách các giá trị được gọi là xu và một danh sách khác được gọi là số lượng của samelength. Giá trị của đồng xu thứ i là đồng xu [i] và chúng tôi hiện có số lượng [i] số đồng xu thứ i.
Vì vậy, nếu đầu vào giống như tiền xu =[1, 2, 5] số lượng =[1, 2, 1], thì đầu ra sẽ là 10, vì chúng ta có thể có tổng số tiền xu riêng biệt sau [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.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
Định nghĩa một hàm rec (). Điều này sẽ đưa tô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
Ví dụ
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))
Đầu vào
[1, 2, 5], [1, 2, 1]
Đầu ra
10