Chương trình đếm số tổ hợp đồng xu đạt mục tiêu trong Python

Mô tả bài toán

Cho danh sách các đồng xu coins và giá trị amount. Đếm số tổ hợp (thứ tự không quan trọng) có tổng bằng amount. Kết quả lấy modulo 10^9+7.

Ví dụ: coins = [2, 5], amount = 10 → đầu ra 2 (tổ hợp: 5 đồng 2, hoặc 2 đồng 5).

Giải thuật (Quy hoạch động - Coin Change 2)

1. m = 10**9 + 7.
2. Khởi tạo mảng dp kích thước amount+1 toàn 0, dp[0] = 1.
3. Với mỗi đồng xu d:
   • Với i từ 1 đến amount: nếu i >= d thì dp[i] = (dp[i] + dp[i-d]) % m.
4. Trả về dp[amount].

Ví dụ mã Python

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))

Đầu vào

[2, 5], 10

Đầu ra

2