पायथन में अद्वितीय पथ

मान लीजिए कि कोई रोबोट n x m ग्रिड (n पंक्तियाँ और m कॉलम) के ऊपरी-बाएँ कोने में स्थित है। रोबोट किसी भी समय केवल नीचे की ओर या दाईं ओर ही घूम सकता है। रोबोट ग्रिड के निचले-दाएँ कोने तक पहुँचना चाहता है (नीचे चित्र में 'END' अंकित है)। तो हमें यह पता लगाना होगा कि कितने संभावित अनूठे रास्ते हैं? उदाहरण के लिए यदि m =3 और n =2, तो ग्रिड नीचे जैसा होगा -

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

1. दाएं → दाएं → नीचे
2. दाएं → नीचे → दाएं
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]
• रिटर्न डीपी[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