Python प्रोग्राम - अधिकतम k लगातार गेम जीतने के तरीकों की गिनती

दो संख्याएं n और k दी गई हैं। यहां n उन गेम की संख्या दर्शाता है जिन्हें हम खेलने जा रहे हैं। हमें उन तरीकों की संख्या खोजनी है जिनसे हम लगातार k या उससे कम गेम जीत सकते हैं। यदि उत्तर बहुत बड़ा है तो परिणाम को 10^9 + 7 से मोड करें।

उदाहरण

इनपुट: n = 3, k = 2

आउटपुट: 7

व्याख्या: लगातार 2 या उससे कम बार जीतने के संभावित तरीके हैं: ["LLL", "WLL", "LWL", "LLW", "WWL", "LWW", "WLW"]।

एल्गोरिदम (डायनामिक प्रोग्रामिंग)

1. m := 10^9 + 7
2. dp(i, K) फंक्शन परिभाषित करें:
   • यदि i >= n or K > k: K <= k हो तो true लौटाएं, अन्यथा false
   • (dp(i + 1, 0) % m + dp(i + 1, K + 1) % m) लौटाएं
3. मुख्य विधि से dp(0, 0) % m लौटाएं

Python कार्यान्वयन

def solve(n, k):
    m = 10**9 + 7
    def dp(i, K):
        if i >= n or K > k:
            return K <= k
        return (dp(i + 1, 0) + dp(i + 1, K + 1)) % m
    return dp(0, 0) % m

n = 4
k = 2
print(solve(n, k))  # आउटपुट: 13 (मूल आउटपुट 5 गलत प्रतीत होता है)

इनपुट/आउटपुट

Input: 4, 2
Output: 13

नोट: मूल कोड में m = 1**9 + 7 था जो गलत है (1**9 = 1)। सही है 10**9 + 7। साथ ही मूल आउटपुट 5 गलत है; n=4, k=2 के लिए सही उत्तर 13 है।