Tổng đường đi nhỏ nhất trong C++

Giả sử chúng ta có ma trận m x n chứa các số nguyên không âm, tìm đường đi từ góc trên bên trái đến góc dưới bên phải sao cho tổng các số trên đường đi là nhỏ nhất. Chỉ được di chuyển xuống hoặc phải tại bất kỳ thời điểm nào. Ví dụ, ma trận:

Kết quả là 7, đường đi: 1,3,1,1,1 (tổng nhỏ nhất).

Các bước thực hiện:

• a := số hàng, b := số cột
• i := a – 1, j := b - 1
• while j >= 0
  • matrix[a, j] := matrix[a, j] + matrix[a, j + 1]
  • giảm j 1
• while i >= 0
  • matrix[i, b] := matrix[i, b] + matrix[i + 1, b]
  • giảm i 1
• j := b - 1 và i := hàng - 1
• while i >= 0
  • while j >= 0
    • matrix[i, j] := matrix[i, j] + min(matrix[i, j + 1], matrix[i + 1, j])
    • giảm j 1
  • j := b - 1
  • i := i - 1
• return matrix[0, 0]

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

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])

Input

[[1,3,1],[1,5,1],[4,2,1]]

Output

7