Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid.

unique_path_with_obstacles.cpp

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int numRows = obstacleGrid.size();
        int numCols = obstacleGrid[0].size();
        
        if (numRows == 0 || numCols == 0 ||
            obstacleGrid[numRows - 1][numCols - 1] == 1) {
            return 0;
        }
        
        vector<int> row(numCols, 0);
        row[numCols - 1] = 1;
        
        for (int i = numRows - 1; i >= 0; i--) {
            for (int j = numCols - 1; j >= 0; j--) {
                if (obstacleGrid[i][j] == 1) {
                    row[j] = 0;
                } else if (j < numCols - 1) {
                    row[j] += row[j + 1];
                }
            }
        }
        
        return row[0];
    }
};