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