63. 不同路径 II
#动态规划 2025-01-21

62. 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> data(m, vector<int>(n, 1));
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                data[i][j] = data[i-1][j] + data[i][j-1];
            }
        }
        return data[m-1][n-1];
    }
};

第一行和第一列初始化为 1（这里全部初始化为1，返回除开第一行和第一列都会被动态改变，且不影响公式）。这是因为，第一行只能从左边过来，第一列只能从上面过来，在没有其他路径。

除开第一行和第一列，它们都遵循一个公式，图解见下：data[i][j] = data[i-1][j] + data[i][j-1]

image-20250121174221805

63. 不同路径 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();    // 行
        int n = obstacleGrid[0].size(); // 列
        vector<vector<int>> data(m, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] != 1) {
                data[0][i] = 1;
                continue;
            }
            break;
        }
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] != 1) {
                data[i][0] = 1;
                continue;
            }
            break;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {  // 遇到障碍物
                    data[i][j] = 0;
                } else {
                    data[i][j] = data[i - 1][j] + data[i][j - 1];
                }
            }
        }
        return data[m - 1][n - 1];
    }
};

把二维数组所有元素初始化为 0，提前处理第一行和第二行存在障碍物情况。

没有遇到障碍物，代表通行没有问题，标记为 1，否则标记为 0，因为不可能有路径能走到这里了。

至于中间的障碍物，我们在遍历的过程中再去处理，如果遇到障碍物标记为 0 就好了，表示其他路径不可能从这里通过，好不影响公式的正确使用。