C++ में न्यूनतम पथ योग (Minimum Path Sum)

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

आउटपुट 7 होगा, पथ होगा 1,3,1,1,1, यह योग को न्यूनतम करेगा।

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

• a := पंक्तियों की संख्या, b := कॉलम की संख्या
• i := a – 1, j := b - 1
• जब तक j >= 0:
  • matrix[a, j] := matrix[a, j] + matrix[a, j + 1]
  • j को 1 घटाएं
• जब तक i >= 0:
  • matrix[i, b] := matrix[i, b] + matrix[i + 1, b]
  • i को 1 घटाएं
• j := b - 1 और i := row - 1
• जब तक i >= 0:
  • जब तक j >= 0:
    • matrix[i, j] := matrix[i, j] + matrix[i, j + 1] और matrix[i + 1, j] का न्यूनतम
    • j को 1 घटाएं
  • j := b - 1
  • i := i - 1
• matrix[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])

इनपुट

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

आउटपुट

7