Python的最小路径总和

假设我们有一个用非负整数填充的amxn矩阵，找到一条从左上角到右下角的路径，该路径将沿其路径的所有数字的总和最小化。只能在任何时间点上下移动。因此，例如，如果矩阵如下所示

131151421

输出将是7，路径将是1,3,1,1,1，这将使总和最小

让我们看看步骤-

a：=行数，b：=列数

i：=a–1，j：=b–1

当j>=0时

矩阵[a，j]：=矩阵[a，j]+矩阵[a，j+1]

将j减1

当我>=0时

矩阵[i，b]：=矩阵[i，b]+矩阵[i+1，b]

将我减少1

j：=b–1和i：=row–1

当我>=0时

矩阵[i，j]：=矩阵[i，j]+矩阵[i，j+1]和矩阵[i+1，j]的最小值

将j减1

当j>=0时

j：=b–1

我：=我–1

返回矩阵[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