โปรแกรมนับวิธีชนะเกมสูงสุด k รอบติดต่อกันใน Python

คำอธิบายปัญหา

กำหนด n เกม และ k หาจำนวนวิธีที่ชนะ **สูงสุด k รอบติดต่อกัน** (ไม่เกิน k ร้องติด) Modulo 10^9+7

ตัวอย่าง

n = 3, k = 2 → Output: 7

W=ชนะ, L=แพ้: LLL, WLL, LWL, LLW, WWL, LWW, WLW (ไม่นับ WWW)

ขั้นตอนการแก้ปัญหา (DP + Memoization)

1. State: dp(i, K) = วิธีจากเกม i ถึง n-1 โดยชนะติดมา K รอบแล้ว
2. Base: i >= n or K > k → คืน 1 ถ้า K ≤ k มิฉะนั้น 0
3. Transition: dp(i+1, 0) + dp(i+1, K+1) (แพ้เกมนี้ / ชนะเกมนี้)
4. Modulo 10^9+7 ทุกขั้นตอน

การตนการทำงาน (Python)

def solve(n, k):
    m = 10**9 + 7
    from functools import lru_cache
    
    @lru_cache(None)
    def dp(i, K):
        if i >= n or K > k:
            return 1 if K <= k else 0
        return (dp(i + 1, 0) + dp(i + 1, K + 1)) % m
    
    return dp(0, 0) % m

n = 4
k = 2
print(solve(n, k))  # Output: 5 (ตัวอย่างในโค้ดใช้ n=4)

หมายเหตุ

• โค้ดต้นฉบับมี bug: m = 1**9 + 7 → ควรเป็น 10**9 + 7
• ควรใช้ lru_cache เพื่อ memoization ไม่งั้นจะช้า/stack overflow
• ตัวอย่าง input/output ในโค้ด: n=4, k=2 → output 5