在 C++ 中的最小路径和

假设我们有一个 m x n 矩阵，其中填充了非负整数，请找到一条从左上角到右下角的路径，使路径上所有数字之和最小。任何时候只能向下或向右移动。例如，如果矩阵如下所示

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

我们来看看步骤 -

• a := 行数，b := 列数

• i := a – 1，j := b - 1

• while j >= 0

  • matrix[a, j] := matrix[a, j] + matrix[a, j + 1]

  • j 减 1

• while i >= 0

  • matrix[i, b] := matrix[i, b] + matrix[i + 1, b]

  • i 减 1

• j := b - 1 和 i := 行 - 1

• while i >= 0

  • while j >= 0

    • matrix[i, j] := matrix[i, j] + matrix[i, j + 1] 和 matrix[i + 1, j] 的最小值

    • j 减 1

  • j := b - 1

  • i := i - 1

• 返回 matrix[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

Arnab Chakraborty

更新日期： 2020 年 4 月 28 日

171 次浏览

开始您的职业

完成课程后取得认证

开始