โปรแกรมนับจำนวนวิธีทำเงินทอนถึงเป้าหมายใน Python

สมมติว่ามีรายการเหรียญ coins และค่า amount ต้องการหาจำนวนวิธีรวมเป็น amount หากมากมาย mod 10^9+7

ตัวอย่าง: coins = [2, 5], amount = 10 ผลลัพธ์ 2 วิธี: [2,2,2,2,2], [5,5]

ขั้นตอนการแก้ปัญหา

1. m = 10**9 + 7
2. dp ขนาด amount+1 เติม 0, dp[0] = 1
3. วนแต่ละเหรียญ d:
   • วน i จาก 1 ถึง amount:
     • ถ้า i-d >= 0: dp[i] += dp[i-d]
4. คืน dp[-1] % m

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

class Solution:
    def solve(self, coins, amount):
        dp = [0] * (amount + 1)
        dp[0] = 1
        for d in coins:
            for i in range(1, len(dp)):
                if i - d >= 0:
                    dp[i] += dp[i - d]
        return dp[-1] % (10 ** 9 + 7)

ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))

อินพุต

[2, 5], 10

เอาต์พุต

2