পাইথনে 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 के समान है तो true, अन्यथा false) लौटाएं
• 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 int(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

আউটপুট

9