63. Unique Paths II
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tính số lượng đường đi duy nhất từ góc bên trái đến góc dưới bên phải của một grid m x n, trong đó:
Robot chỉ có thể di chuyển xuống hoặc sang phải tại mỗi bước. Nếu có chướng ngại vật trên đường đi, không thể đi qua ô đó
Approach - Bottom up DP - 2 dimensional
Tạo một mảng dp 2 chiều, trong đó dp[i][j] là số đường đi để tới ô (i, j) . Công thức chuyển
(i, j) là obstacle (obstacleGrid[i][j] === 1 ) thì dp[i][j] = 0 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (nếu tồn tại)dp = 1Solution
1function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
2 const rows = obstacleGrid.length;
3 const cols = obstacleGrid[0].length;
4 if (obstacleGrid[0][0] === 1) return 0
5 const dp: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));
6 dp[0][0] = 1;
7 for (let i = 0; i < rows; i++) {
8 for (let j = 0; j < cols; j++) {
9 if (obstacleGrid[i][j] === 1) dp[i][j] = 0;
10 else {
11 if (i > 0) dp[i][j] += dp[i - 1][j];
12 if (j > 0) dp[i][j] += dp[i][j - 1];
13 }
14 }
15 }
16 return dp[rows - 1][cols - 1]
17};dp[i][j] = dp[i - 1][j] + dp[i][j - 1]1dp[i][j] = dp[i - 1][j] + dp[i][j - 1]Tuy nhiên, công thức này chỉ đúng khi cả hai chỉ số i-1 và j-1 đều hợp lệ (không âm). Nếu bạn áp dụng công thức này với i = 0 hoặc j = 0, bạn sẽ truy cập vào dp[-1][j] hoặc dp[i][-1], điều này sẽ gây lỗi hoặc lấy giá trị không xác định trong mảng.
i = 0 (hàng đầu tiên): Không có ô nào phía trên, chỉ có thể đi từ trái sangj = 0 (cột đầu tiên): Không có ô nào bên trái, chỉ có thể đi từ trên xuốngDo đó, bạn phải kiểm tra:
i > 0 thì mới cộng dp[i - 1][j] j > 0 thì mới cộng dp[i][j - 1]Approach - 1 Dimensional DP
dp kích thước n (số cột).1function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
2 const rows = obstacleGrid.length;
3 const cols = obstacleGrid[0].length
4
5 if (obstacleGrid[0][0] === 1) return 0;
6 const dp: number[] = Array(cols).fill(0);
7 dp[0] = 1;
8 for (let i = 0; i < rows; i++) {
9 for (let j = 0; j < cols; j++) {
10 if (obstacleGrid[i][j] === 1) dp[j] = 0
11 else if (j > 0) dp[j] += dp[j - 1]
12 }
13 }
14 return dp[cols - 1]
15};dp[j] là số đường đi đến ô (i, j) dp[j - 1] )dp sẽ chứa số đường đi cho dòng hiện tạiGiả sử khi bạn chỉ dùng mảng 1 chiều dp[j] với j là cols
(i, j):(i-1, j) (tức là từ dòng trên, cùng cột).(i, j-1) (tức là dòng hiện tại, cột trước đó).Ý nghĩa của dp[j] và dp[j - 1] trong tối ưu 1 chiều
Minh họa
Mảng 1 chiều không lưu lại toàn bộ trạng thái như 2D
Cách cập nhật mảng 1 chiều (giả lập từng bước)
Giả sử grid 3x3, không obstacle:
Khởi tạo
1dp = [1, 0, 0]Duyệt từng dòng (row):
Row 0 (i = 0):
dp sau row 0: `[1,#### Row 1 (i = 1):
dp sau row 1: `[1,#### Row 2 (i = 2):
dp sau row 2: `[1,---
Tóm lại
dp[j] trước khi cập nhật.dp[j-1].