分析

• 本题的考点：动态规划。

• 状态表示f[i][j]：从起点到达坐标点(i, j)的方案数。

• 状态转移：f[i][j] = f[i-1][j] + f[i][j-1]。另外第一行和第一列上的坐标不一定有达到的方案，因此第一行、第一列不能直接被赋值为1。

• 和Leetcode 0062 不同路径区别是存在障碍物，如果(i, j)存在障碍物的话，则直接跳过即可。

代码

• C++

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obs) {

        int m = obs.size(), n = obs[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (!obs[i][j]) {
                    if (!i && !j) f[i][j] = 1;
                    else {
                        if (i) f[i][j] += f[i - 1][j];
                        if (j) f[i][j] += f[i][j - 1];
                    }
                }
        return f[m - 1][n - 1];
    }
};

• Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obs) {

        int m = obs.length, n = obs[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) 
                if (obs[i][j] == 0) {
                    if (i == 0 && j == 0) f[i][j] = 1;
                    else {
                        if (i != 0) f[i][j] += f[i - 1][j];
                        if (j != 0) f[i][j] += f[i][j - 1];
                    }
                }
        return f[m - 1][n - 1];
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times m)$，m、n为行数、列数。

• 空间复杂度：$O(n \times m)$。