Số Cách Tung Xúc Xắc Để Đạt Tổng Mục Tiêu (Dice Roll Target Sum) - DP

Đề bài: Có d cái xúc xắc, mỗi cái f mặt (1..f). Tìm số cách tung để tổng mặt lên = target. Kết quả modulo 10^9+7.

Ví dụ: d=2, f=6, target=7 → 6 cách: (1,6)(2,5)(3,4)(4,3)(5,2)(6,1).

Dynamic Programming

dp[i][t] = số cách dùng i+1 xúc xắc đạt tổng t.

• Base: dp[0][j] = 1 nếu 1 ≤ j ≤ f, else 0.
• Transition: dp[i][t] = sum(dp[i-1][t-face] for face in 1..f if t-face > 0).
• Kết quả: dp[d-1][target] % MOD.

Code Python (Bottom-up DP)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (target + 1) for _ in range(d)]
        
        # Base case: 1 xúc xắc
        for face in range(1, f + 1):
            if face <= target:
                dp[0][face] = 1
        
        # Fill DP table
        for i in range(1, d):
            for t in range(1, target + 1):
                for face in range(1, f + 1):
                    if t - face > 0:
                        dp[i][t] = (dp[i][t] + dp[i-1][t-face]) % MOD
        
        return dp[d-1][target] % MOD

# Test
ob = Solution()
print(ob.numRollsToTarget(2, 6, 7))  # 6
print(ob.numRollsToTarget(1, 6, 3))  # 1
print(ob.numRollsToTarget(30, 30, 500))  # Large test

Tối ưu Space: 1D DP

Chỉ cần hàng trước → dùng 1 mảng, duyệt t từ lớn đến nhỏ (hoặc dùng mảng temp).

def numRollsToTarget(self, d: int, f: int, target: int) -> int:
    MOD = 10**9 + 7
    dp = [0] * (target + 1)
    for face in range(1, f + 1):
        if face <= target:
            dp[face] = 1
    
    for _ in range(1, d):
        new_dp = [0] * (target + 1)
        for t in range(1, target + 1):
            for face in range(1, f + 1):
                if t - face > 0:
                    new_dp[t] = (new_dp[t] + dp[t-face]) % MOD
        dp = new_dp
    
    return dp[target]

Phân tích độ phức tạp

• Time: O(d * target * f)
• Space: O(target) (1D) hoặc O(d * target) (2D)

Kết luận

Bài toán DP kinh điển "number of ways". Lưu ý modulo ở mỗi bước cộng để tránh overflow (dù Python big int, nhưng modulo sớm nhanh hơn).