[LeetCode] Unique Paths I && II

Unique Paths I

Problem Statement (link):

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.

Analysis:
First, notice that this is a DP problem, the number of paths to reach (i, j) equals to the number of paths to reach (i-1, j) + the number of paths to reach (i, j-1), except the first row and column, where the number of paths are all 1.

It's obvious that we could use a 2D DP to solve it. However, if we consider reusing a 1D DP vector, we could solve it with O(n) time complexity. The time complexity is O(m*n).

Code:
Sol 1: 2D DP

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> res(m, vector<int>(n, 0));
        for (int i=0; i<m; i++)
            res[i][0]=1;
        for (int j=0; j<n; j++)
            res[0][j]=1;

        for (int i=1; i<m; i++)

            for (int j=1; j<n; j++)
                res[i][j]=res[i-1][j]+res[i][j-1];
        return res[m-1][n-1];
    }
};

Sol 2: 1D DP

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> res(n, 1);
        for (int i=1; i<m; i++)
            for (int j=1; j<n; j++)
                res[j]=res[j-1]+res[j];
        return res[n-1];
    }
};

Unique Paths II

Problem Statement (link):

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.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.

Analysis:
The basic idea is same as the previous problem. Just a few special cases that we need to take care of when encounter obstacles.

- For the first row and first column, once we encounter an obstacle, that space and all the following spaces should be set to 0 as we couldn't reach these places;
- For the rest spaces, once we encounter an obstacle, that space should be set to 0; otherwise, we sum up the value in its left and top and put the sum to that space. Note that the summation takes case of the cases where either or both its left and top are 0.

The space complexity is O(n) and time complexity is O(m*n).

Code:

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

        // initialize using first row
        for (int j=0; j<n; j++) {
            if (obstacleGrid[0][j]==1)
                break;
            res[j]=1;
        }

        for (int i=1; i<m; i++) {
            for (int j=0; j<n; j++) {
                // assign the fist element
                if (j==0 && (obstacleGrid[i][0]==1 || res[0]==0)) {
                    res[0]=0;
                    continue;
                }
                else if (j==0 && obstacleGrid[i][0]==0) {
                    res[0]=1;
                    continue;
                }

                // the rest
                if (obstacleGrid[i][j]==0)
                    res[j]=res[j-1]+res[j];
                if (obstacleGrid[i][j]==1)
                    res[j]=0;
            }
        }
        return res[n-1];
    }
};