k चाल चलकर वापस पहली स्थिति पर आने के तरीकों की संख्या ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हम n लंबाई की सूची में स्थिति 0 पर हैं, और प्रत्येक चरण में हम एक स्थान दाएं या बाएं जा सकते हैं (सीमा पार किए बिना), या उसी स्थिति पर रह सकते हैं। अब यदि हम ठीक k चरण ले सकते हैं, तो हमें यह ढूंढना है कि हम कितने अद्वितीय तरीकों से चलकर वापस इंडेक्स 0 पर पहुंच सकते हैं। यदि उत्तर बहुत बड़ा है तो इसे 10^9 + 7 से मॉड्यूलो करके लौटाएं।

उदाहरण के लिए, यदि इनपुट n = 7, k = 4 है, तो आउटपुट 9 होगा, क्योंकि कार्य हैं:

[दाएं, दाएं, बाएं, बाएं],
[दाएं, बाएं, दाएं, बाएं],
[रहें, रहें, रहें, रहें],
[दाएं, बाएं, रहें, रहें],
[रहें, रहें, दाएं, बाएं],
[दाएं, रहें, रहें, बाएं],
[दाएं, रहें, बाएं, रहें],
[रहें, दाएं, बाएं, रहें],
[रहें, दाएं, रहें, बाएं],

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

m := 10^9 + 7
N := लंबाई
एक फ़ंक्शन dp() परिभाषित करें। यह i, jumps लेगा
यदि jumps 0 के समान है, तो
- (सत्य लौटाएं जब i 0 के समान हो, अन्यथा असत्य)
count := dp(i, jumps - 1)
यदि i >= 0, तो
- count := count + dp(i + 1, jumps - 1)
यदि i <= N - 1, तो
- count := count + dp(i - 1, jumps - 1)
count लौटाएं
मुख्य विधि से निम्न करें:
dp(0, n) mod m लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, length, n):
        MOD = 10 ** 9 + 7
        N = length
        def dp(i, jumps):
            if jumps == 0:
                return +(i == 0)
            count = dp(i, jumps - 1)
            if i >= 0:
                count += dp(i + 1, jumps - 1)
            if i <= N - 1:
                count += dp(i - 1, jumps - 1)
            return count
        return dp(0, n) % MOD

ob = Solution()
n = 7
k = 4
print(ob.solve(n, k))

इनपुट

7, 4