Giả sử có ma trận m x n chứa số nguyên không âm, tìm đường đi từ góc trên trái đến góc dưới phải sao cho tổng các số trên đường đi nhỏ nhất. Chỉ di chuyển xuống hoặc phải tại mọi thời điểm. Ví dụ ma trận:
| 1 | 3 | 1 |
| 1 | 5 | 1 |
| 4 | 2 | 1 |
Kết quả 7, đường đi 1,3,1,1,1 cho tổng nhỏ nhất.
Các bước −
- a := số hàng, b := số cột
- i := a - 1, j := b - 1
- khi j >= 0
- matrix[a][j] := matrix[a][j] + matrix[a][j+1]
- giảm j 1
- khi i >= 0
- matrix[i][b] := matrix[i][b] + matrix[i+1][b]
- giảm i 1
- j := b - 1, i := hàng - 1
- khi i >= 0
- khi 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
- khi j >= 0
- trả về matrix[0][0]
Xem triển khai sau −
Ví dụ
class Solution(object): def minPathSum(self, grid): 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]) ob1 = Solution() print(ob1.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
Đầu vào
[[1,3,1],[1,5,1],[4,2,1]]
Kết quả
7