मान लीजिए कि कोई रोबोट n x m ग्रिड (n पंक्तियाँ और m कॉलम) के ऊपरी-बाएँ कोने में स्थित है। रोबोट किसी भी समय केवल नीचे की ओर या दाईं ओर ही घूम सकता है। रोबोट ग्रिड के निचले-दाएँ कोने तक पहुँचना चाहता है (नीचे चित्र में 'END' अंकित है)। तो हमें यह पता लगाना होगा कि कितने संभावित अनूठे रास्ते हैं? उदाहरण के लिए यदि m =3 और n =2, तो ग्रिड नीचे जैसा होगा -
रोबो | <टीडी>|
| <टीडी> END |
आउटपुट 3 होगा, इसलिए प्रारंभ स्थिति से अंतिम स्थिति तक पहुंचने के लिए कुल 3 अलग-अलग तरीके हैं। ये रास्ते हैं -
- दाएं → दाएं → नीचे
- दाएं → नीचे → दाएं
- नीचे → दाएँ → दाएँ
आइए चरणों को देखें -
- हम इसे हल करने के लिए गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे
- चलो पंक्ति :=n और col :=m, क्रम n x m की तालिका DP बनाएं और इसे -1 से भरें
- DP[पंक्ति - 2, कॉलम - 1] :=1
- मैं के लिए 0 से कर्नल की श्रेणी में
- DP[n – 1, i] :=1
- मैं के लिए 0 से पंक्ति की सीमा में
- DP[i, col - 1] :=1
- मैं श्रेणी पंक्ति -2 से नीचे -1 के लिए
- जे के लिए col -2 से नीचे -1
- . की श्रेणी में
- DP[i, j] :=DP[i + 1, j] + DP[i, j + 1]
- जे के लिए col -2 से नीचे -1
- रिटर्न डीपी[0, 0]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Solution(object): def uniquePaths(self, m, n): row = n column = m dp = [[-1 for i in range(m)] for j in range(n)] dp[row-2][column-1] = 1 for i in range(column): dp[n-1][i] = 1 for i in range(row): dp[i][column-1]=1 for i in range(row-2,-1,-1): for j in range(column-2,-1,-1): dp[i][j] = dp[i+1][j] + dp[i][j+1] return dp[0][0] ob1 = Solution() print(ob1.uniquePaths(10,3))
इनपुट
10 3
आउटपुट
55