Chương trình đếm số cách ném xúc xắc để đạt tổng cho trước trong Python

Cho số xúc xắc n, số mặt faces, và tổng mục tiêu total. Đếm số cách ném để đạt tổng đó, kết quả modulo 10^9+7.

Ví dụ

Đầu vào: n=2, faces=6, total=8.
Đầu ra: 5 (các cặp: (2,6),(6,2),(3,5),(5,3),(4,4)).

Thuật toán

1. Khởi tạo mảng dp kích thước total+1 toàn 0.
2. Đặt dp[face] = 1 cho face từ 1 đến min(faces, total).
3. Lặp n-1 lần:
   • Duyệt j từ total xuống 1:
     • dp[j] = sum(dp[j-f] for f in 1..faces if j-f >= 1).
4. Trả về dp[total] % (10^9+7).

Mã nguồn Python

class Solution:
    def solve(self, n, faces, total):
        m = 10**9 + 7
        dp = [0] * (total + 1)
        for face in range(1, min(faces, total) + 1):
            dp[face] = 1
        for _ in range(n - 1):
            for j in range(total, 0, -1):
                dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1)
        return dp[-1] % m

ob = Solution()
print(ob.solve(2, 6, 8))

Đầu vào / Đầu ra

Input: 2,6,8
Output: 5