Tổng đường dẫn tối thiểu trong C ++

Giả sử chúng ta có một ma trận m x n chứa đầy các số nguyên không âm, hãy tìm một đường đi từ góc trên cùng bên trái đến góc dưới cùng bên phải để nhỏ nhất tổng của tất cả các số dọc theo đường đi của nó. Các chuyển động chỉ có thể đi xuống hoặc sang phải tại bất kỳ thời điểm nào. Vì vậy, ví dụ, nếu ma trận như dưới đây

1	3	1
1	5	1
4	2	1

Đầu ra sẽ là 7, đường dẫn sẽ là 1,3,1,1,1, điều này sẽ giảm thiểu tổng

Hãy để chúng tôi xem các bước -

a:=số hàng, b:=số cột
i:=a - 1, j:=b - 1
trong khi j> =0
- ma trận [a, j]:=ma trận [a, j] + ma trận [a, j + 1]
- giảm j đi 1
trong khi tôi> =0
- ma trận [i, b]:=ma trận [i, b] + ma trận [i + 1, b]
- giảm tôi đi 1
j:=b - 1 và i:=row - 1
trong khi tôi> =0
- trong khi j> =0
  - ma trận [i, j]:=ma trận [i, j] + cực tiểu của ma trận [i, j + 1] và ma trận [i + 1, j]
  - giảm j đi 1
- j:=b - 1
- i:=i - 1
ma trận trả về [0, 0]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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