หาจำนวนผลรวมเหรียญที่แตกต่างกันได้จากเหรียญและจำนวนใน Python

มีลิสต์ coins (ค่าเหรียญ) และ quantities (จำนวนเหรียญแต่ละชนิด) หาจำนวนผลรวมที่แตกต่างกันที่ทำได้จากการนำเหรียญมารวมกัน (ต้องใช้อย่างน้อย 1 เหรียญ)

ตัวอย่าง: coins = [1, 2, 5], quantities = [1, 2, 1] → 10 ผลรวม (1,2,3,4,5,6,7,8,9,10)

แนวทาง (DFS + Set)

1. ฟังก์ชัน rec(i, res): พิจารณาเหรียญชนิดที่ i ผลรวมสะสม res
2. ลองใช้เหรียญชนิด i จำนวน 0 ถึง quantities[i] เหรียญ
3. เก็บผลรวมทั้งหมดใน Set fres
4. คืนค่า len(fres) - 1 (ลบกรณีใช้ 0 เหรียญ)

ตัวอย่างโค้ด

class Solution:
    def solve(self, coins, quantities):
        def rec(i, res):
            if i == len(coins):
                return
            for k in range(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))  # 10

อินพุต

[1, 2, 5], [1, 2, 1]

เอาต์พุต

10