पायथन में न्यूनतम पथ योग

मान लीजिए कि हमारे पास गैर-ऋणात्मक पूर्णांकों से भरा एक m x n मैट्रिक्स है, तो ऊपरी बाएं कोने से नीचे दाएं कोने तक एक पथ खोजें जो इसके पथ के साथ सभी संख्याओं के योग को कम करता है। आंदोलन किसी भी समय केवल नीचे या दाएं हो सकते हैं। तो उदाहरण के लिए, यदि मैट्रिक्स नीचे जैसा है

1	3	1
1	5	1
4	2	1

आउटपुट 7 होगा, पथ 1,3,1,1,1 होगा, इससे योग कम हो जाएगा

आइए चरणों को देखें -

a :=पंक्तियों की संख्या, b :=स्तंभों की संख्या
i :=a – 1, j:=b – 1
जबकि j>=0
- मैट्रिक्स[ए, जे] :=मैट्रिक्स[ए, जे] + मैट्रिक्स[ए, जे + 1]
- j को 1 से घटाएं
जबकि मैं>=0
- मैट्रिक्स[i, b] :=मैट्रिक्स[i, b] + मैट्रिक्स[i + 1, b]
- i 1 से घटाएं
j :=b – 1 और i :=Row – 1
जबकि मैं>=0
- जबकि j>=0
  - मैट्रिक्स[i, j] :=मैट्रिक्स[i, j] + न्यूनतम मैट्रिक्स[i, j + 1] और मैट्रिक्स[i + 1, j]
  - j को 1 से घटाएं
- j :=b – 1
- i :=i – 1
रिटर्न मैट्रिक्स[0, 0]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution(object):
   def minPathSum(self, grid):
      row = len(grid)-1
      column = len(grid[0])-1
      i=row-1
      j=column-1
      while j>=0:
         grid[row][j]+=grid[row][j+1]
         j-=1
      while i>=0:
         grid[i][column]+=grid[i+1][column]
         i-=1
      j=column-1
     i = row-1
      while i>=0:
         while j>=0:
            grid[i][j] += min(grid[i][j+1],grid[i+1][j])
            j-=1
         j=column-1
         i-=1
      return(grid[0][0])
ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

इनपुट

[[1,3,1],[1,5,1],[4,2,1]]