Python 中的最小路徑和

假設我們有一個填滿非負整數的 m x n 矩陣，找出從左上角到右下角的路徑，可使沿該路徑的所有數字之和最小。任何時候只能向下或向右移動。例如，如果矩陣如下所示：

131
151
421

輸出將為 7，路徑將為 1,3,1,1,1，這將最小化總和

讓我們看看這些步驟 −

  • a := 行數，b := 列數
  • i := a – 1，j := b – 1
  • while j >= 0
    • matrix[a, j] := matrix[a, j] + matrix[a, j + 1]
    • j 減 1
  • while i >= 0
    • matrix[i, b] := matrix[i, b] + matrix[i + 1, b]
    • i 減 1
  • j := b – 1，i := row – 1
  • while i >= 0
    • while 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

更新於： 2020 年 5 月 4 日

667 次瀏覽

開啟你的 職業生涯

完成課程認證

開始
廣告