मान लीजिए कि हम n लंबाई सूची की स्थिति 0 पर हैं, और प्रत्येक चरण पर, हम दाएँ एक स्थान या बाएँ एक स्थान (सीमा से अधिक नहीं) जा सकते हैं, या उसी स्थिति में रह सकते हैं। अब अगर हम बिल्कुल k कदम उठा सकते हैं, तो हमें यह पता लगाना होगा कि हम कितने अनूठे कदम उठा सकते हैं और इंडेक्स 0 पर वापस पहुंच सकते हैं। यदि उत्तर बहुत बड़ा है तो इसे मॉड 10^9 + 7.
इसलिए, यदि इनपुट n =7 k =4 जैसा है, तो आउटपुट 9 होगा, जैसा कि क्रियाएं हैं-
- [दाएं, दाएं, बाएं, बाएं],
- [दाएं, बाएं, दाएं, बाएं],
- [रहें, रहें, रहें, रहें],
- [दाएं, बाएं, रहें, रहें],
- [रहें, रहें, दाएं, बाएं],
- [राइट, स्टे, स्टे, लेफ्ट],
- [राइट, स्टे, लेफ्ट, स्टे],
- [रहो, दाएं, बाएं, रहो],
- [रहने, दाएं, रहने, बाएं],
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- म :=10^9 + 7
- N :=लंबाई
- एक फ़ंक्शन को परिभाषित करें dp() । यह मुझे ले जाएगा, कूदता है
- यदि कूद 0 के समान है, तो
- वापसी (सच है जब मैं 0 के समान है, अन्यथा गलत)
- गिनती :=dp(i, कूद - 1)
- अगर मैं>=0, तो
- गिनती:=गिनती + डीपी(i + 1, कूद - 1)
- अगर मैं <=एन -1, तो
- गिनती:=गिनती + डीपी(i-1, कूदता है-1)
- वापसी की संख्या
- मुख्य विधि से निम्न कार्य करें:
- रिटर्न डीपी(0, एन) मॉड एम
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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
आउटपुट
9