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 次浏览

开启你的 职业生涯

完成课程认证

开始
广告