Chương trình Python đếm số cách thắng tối đa k ván liên tiếp

Cho n ván chơi, k là số lần thắng liên tiếp tối đa cho phép. Tìm số chuỗi kết quả (W=thắng, L=thua) độ dài n không chứa k+1 ký tự W liên tiếp. Kết quả mod 10⁹+7.

Ví dụ

Input: n = 3, k = 2

Output: 7

Các chuỗi hợp lệ: LLL, WLL, LWL, LLW, WWL, LWW, WLW (loại WWW).

Thuật toán (DP - Đếm chuỗi không có k+1 W liên tiếp)

Định nghĩa dp[i][j]: số cách cho i ván đầu, kết thúc bằng j thắng liên tiếp (j = 0..k).

• Cơ sở: dp[0][0] = 1.
• Chuyển trạng thái:
  • Thua: dp[i+1][0] += sum(dp[i][*])
  • Thắng: dp[i+1][j+1] += dp[i][j] cho j < k.
• Kết quả: sum(dp[n][*]).

Mã nguồn Python (Tối ưu O(n*k))

def solve(n, k):
    MOD = 10**9 + 7
    # dp[j] = số cách kết thúc bằng j thắng liên tiếp
    dp = [0] * (k + 1)
    dp[0] = 1

    for _ in range(n):
        new_dp = [0] * (k + 1)
        total = sum(dp) % MOD
        # Thua: reset về 0 thắng liên tiếp
        new_dp[0] = total
        # Thắng: tăng số thắng liên tiếp
        for j in range(k):
            new_dp[j + 1] = (new_dp[j + 1] + dp[j]) % MOD
        dp = new_dp

    return sum(dp) % MOD

# Test
n = 4
k = 2
print(solve(n, k))  # Output: 13 (ví dụ gốc có lỗi output 5)

Độ phức tạp

• Thời gian: O(n*k)
• Không gian: O(k)

Lưu ý: Code ví dụ gốc dùng đệ quy không memo hóa (chậm, sai mod). Phiên bản trên dùng DP bottom-up đúng và hiệu quả.