C ++中的最小路径总和

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

131
151
421

输出将是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