63. Unique Paths II

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

        vector<vector<int>> dp(m, vector<int>(n));

        dp[0][0] = obstacleGrid[0][0] ? 0 : 1;

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

• T: $O(M \cdot N)$
• S: $O(M \cdot N)$