Unique Paths II

63. 不同路径II

分析

状态定义：f[i][j] 代表从起点 (0, 0) 到达 (i, j) 的路径数
状态转移：
- 如果 obstacleGrid[i][j] == 0，表示当前位置可以走（没有障碍物），我们根据递推公式更新路径数：
  - 如果当前位置是起点 (0, 0)，则 f[0][0] = 1
  - 否则，当前位置的路径数由上方和左方的路径数之和 f[i][j] = f[i-1][j] + f[i][j-1] 得出
- 如果 obstacleGrid[i][j] == 1，说明当前位置有障碍物，不能走到这里，无需处理 f[i][j]，因为初始的 f[i][j] 值为 0
返回最终结果：循环结束后，f[n-1][m-1] 就是从起点到终点的不同路径数

时间复杂度

时间复杂度 O(n * m)

空间复杂度

空间复杂度为 O(n * m)

C++代码

 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


class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        // 初始化 DP 数组
        std::vector<std::vector<int>> f(n, std::vector<int>(m));

        // 遍历每个格子
        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < m; ++ j)
                if (obstacleGrid[i][j] == 0)  // 如果当前格子没有障碍物
                {
                    if (i == 0 && j == 0)  // 起始位置
                        f[i][j] = 1;  // 从起点出发，路径数为 1
                    else
                    {
                        if (i)  // 如果不在第一行
                            f[i][j] += f[i - 1][j];  // 从上方格子来的路径数
                        if (j)  // 如果不在第一列
                            f[i][j] += f[i][j - 1];  // 从左方格子来的路径数
                    }
                }

        return f[n - 1][m - 1];  // 返回右下角的路径数
    }
};