पायथन में अद्वितीय पथ (Unique Paths)

मान लीजिए एक रोबोट n x m ग्रिड (n पंक्तियां और m कॉलम) के शीर्ष-बाएं कोने पर स्थित है। रोबोट किसी भी समय केवल नीचे या दाएं जा सकता है। रोबोट ग्रिड के नीचे-दाएं कोने (आरेख में 'END' से चिह्नित) तक पहुंचना चाहता है। तो हमें ढूंढना है कि कितने संभावित अद्वितीय पथ हैं? उदाहरण के लिए यदि m = 3 और n = 2, तो ग्रिड इस तरह होगा:

रोबो
		END

आउटपुट 3 होगा, यानी प्रारंभिक स्थिति से अंतिम स्थिति तक पहुंचने के कुल 3 अलग-अलग तरीके हैं। ये पथ हैं:

दाएं → दाएं → नीचे
दाएं → नीचे → दाएं
नीचे → दाएं → दाएं

आइए चरण देखें:

हम इसे हल करने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे
row := n और col := m मान लें, n x m क्रम की एक तालिका DP बनाएं और इसे -1 से भरें
DP[row – 2, col - 1] := 1
i को 0 से col तक की रेंज में:
- DP[n – 1, i] := 1
i को 0 से row तक की रेंज में:
- DP[i, col – 1] := 1
i को row -2 से -1 तक डाउन करें:
- j को col -2 से -1 तक डाउन करें:
  - DP[i, j] := DP[i + 1, j] + DP[i, j + 1]
DP[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