C ++中的最小路径总和
假设我们有一个用非负整数填充的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):
"""
:type grid: List[List[int]]
:rtype: int
"""
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])输入值
[[1,3,1],[1,5,1],[4,2,1]]
输出结果
7
热门推荐
10 对患者生日祝福语简短
11 结婚祝福语简短装备
12 周岁祝福语学生文案简短
13 订婚领证祝福语简短精辟
14 导师获奖祝福语大全简短
15 新婚购房祝福语简短精辟
16 牛年祝福语简短的爱人
17 送芒果的祝福语简短
18 送给学长毕业祝福语简短