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

मान लीजिए हमारे पास एक 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 := पंक्ति - 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])

ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))

इनपुट

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

आउटपुट

7