在 C++ 中的最小路徑和

假設我們有一個 m x n 矩陣，其中填充了非負整數，請找到一條從左上角到右下角的路徑，使路徑上所有數字之和最小。任何時候只能向下或向右移動。例如，如果矩陣如下所示

131
151
421

輸出將是 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

更新日期： 2020 年 4 月 28 日

171 次瀏覽

開始您的職業

完成課程後取得認證

開始
廣告