Python 中的最小路径和

pythonserver side programmingprogramming更新于 2025/11/22 15:08:17

假设我们有一个 m x n 矩阵，其中填充了非负整数，找到一条从左上角到右下角的路径，使路径上所有数字的总和最小。在任何时间点，移动只能向下或向右。例如，如果矩阵如下所示

1	3	1
1	5	1
4	2	1

输出将为 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])
ob1 = Solution()
print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))