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