64. Minimum Path Sum

Problem

Bài toán yêu cầu tìm đường đi từ góc bên trái → góc dưới bên phải của một matrix số nguyên không âm, sao cho tổng các số trên đường đi là nhỏ nhất. Bạn chỉ được phép đi sang phải hoặc xuống dưới tại mỗi bước

Approach

Sử dụng DP để lưu lại tổng số nhỏ nhất khi đi đến mỗi ô

Với mỗi ô (i, j) , tổng nhỏ nhất để đến được ô này là giá trị của ô đó cộng với tổng nhỏ nhất của ô bên trái (i, j - 1) hoặc ô phía trên (i - 1, j) chọn giá trị nhỏ hơn

Công thức truy hồi

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1] + grid[i][j])

Khởi tạo hàng đầu tiên và cột đầu tiên vì chỉ có một đường đi đến các ô này (chỉ đi sang phải hoặc xuống dưới)

Time and space complexity

TC: O (rows * cols)

SC: O(1)

Solution

typescripttypescript

1function minPathSum(grid: number[][]): number {
2    const rows = grid.length;
3    const cols = grid[0].length;
4    for (let i = 0; i < rows; i++) {
5        for (let j = 0; j < cols; j++) {
6            if (i === 0 && j === 0) continue
7            else if (i === 0) grid[i][j] += grid[i][j - 1];
8            else if (j === 0) grid[i][j] += grid[i - 1][j]
9            else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
10        }
11    }
12    return grid[rows - 1][cols - 1]
13};

💡

Tóm tắt

Dùng DP, mỗi ô chỉ cần biết tổng nhỏ nhất từ trên hoặc từ trái đến

Khởi tạo hàng/ cột đầu tiên đặc biệt

Duyệt toàn bộ lưới, cập nhật tại chỗ

Kết quả là giá trị ở ô dưới cùng bên phải

💡

Giải thích thêm về hàng đầu tiên

Hàng đầu tiên (i = 0):

Bạn chỉ có thể đi sang phải (tức là từ ô sang [0,rồi , ...),

Bạn không thể đi xuống từ trên vì không có hàng nào phía trên hàng đầu tiên.

Cột đầu tiên (j = 0):

Bạn chỉ có thể đi xuống dưới (tức là từ ô xuống , rồi [2,..),

Bạn không thể đi sang trái vì không có cột nào phía bên trái cột đầu tiên.

Loading content...

1function minPathSum(grid: number[][]): number { 2 const rows = grid.length; 3 const cols = grid[0].length; 4 for (let i = 0; i < rows; i++) { 5 for (let j = 0; j < cols; j++) { 6 if (i === 0 && j === 0) continue 7 else if (i === 0) grid[i][j] += grid[i][j - 1]; 8 else if (j === 0) grid[i][j] += grid[i - 1][j] 9 else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]) 10 } 11 } 12 return grid[rows - 1][cols - 1] 13};