सी++ में न्यूनतम पथ योग

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

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

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

• a:=पंक्तियों की संख्या, b:=स्तंभों की संख्या

• मैं :=a – 1, j :=b-1

• जबकि j>=0

  • मैट्रिक्स [ए, जे]:=मैट्रिक्स [ए, जे] + मैट्रिक्स [ए, जे + 1]

  • j को 1 से घटाएं

• जबकि मैं>=0

  • मैट्रिक्स [i, b]:=मैट्रिक्स [i, b] + मैट्रिक्स [i + 1, b]

  • मैं 1 से घटाता हूं

• j :=b - 1 और i :=row - 1

• जबकि मैं>=0

  • जबकि j>=0

    • मैट्रिक्स [i, j]:=मैट्रिक्स [i, j] + न्यूनतम मैट्रिक्स [i, j + 1] और मैट्रिक्स [i + 1, j]

    • j को 1 से घटाएं

  • जे:=बी - 1

  • मैं :=मैं - 1

• रिटर्न मैट्रिक्स[0, 0]

उदाहरण

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

class Solution(object):
   def minPathSum(self, grid):
      """
      :type grid: List[List[int]]
      :rtype: int
      """
      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])

इनपुट

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

आउटपुट

7