Leetcode Acwing

动态规划 \(O(n^2)\)

在Leetcode 62. 不同路径的基础上稍加限制，我们需要识别一个点是不是障碍，假如是的话就不计算它（默认为0）。稍作注意的是这里是从0开始，需要小心一下边界。

时间复杂度

\(O(n^2)\)

空间复杂度

\(O(n^2)\)

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n;
        if (m) n = obstacleGrid[0].size(); 
        else return 0;

        int f[m][n];
        memset(f, 0, sizeof f);

        for (int i = 0; i < m; i ++)
        {
            for (int j = 0; j < n; j ++)
            {
                if (!obstacleGrid[i][j])
                {
                    if (!i && !j) f[i][j] = 1;
                    if (i) f[i][j] += f[i-1][j];
                    if (j) f[i][j] += f[i][j-1];
                }
            }
        }

        return f[m-1][n-1];
    }
};