Leetcode 63: Unique Paths II (iterative dp, linear space)

leetcode_63c.cpp

#include <iostream>
#include <vector>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int rows = obstacleGrid.size();
    if (rows == 0) return 0;
    int cols = obstacleGrid[0].size();
    if (cols == 0) return 0;
    vector<long> dp(cols);
    dp[0] = (obstacleGrid[0][0] == 1 ? 0 : 1);
    for (int c=1; c<cols; ++c)
        dp[c] = (obstacleGrid[0][c] == 1 ? 0 : dp[c-1]);

    for (int r=1; r<rows; ++r) {
        dp[0] = (obstacleGrid[r][0] == 1 ? 0 : dp[0]); //first column: if obstacle then paths=0 otherwise use previous column value
        for (int c=1; c<cols; ++c) 
            dp[c] = (obstacleGrid[r][c] == 1 ? 0 : dp[c-1] + dp[c]); //previous column to left and previous value in this column, which was for previous row
    }
    return dp[cols-1];
}

int main() {
    vector<vector<int>> obs{{0,0,0},{0,1,0},{0,0,0}}; //{{1}};
    cout << uniquePathsWithObstacles(obs) << "\n";
    return 0;
}