Paths in Matrix

[Question]:

A robot is located at the top-left corner of a m x n grid.

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?

[Analysis]:

C(m, n) = C(m-1, n) + C(m, n-1)
C(m,1) = 1, C(1, n) = 1

Use recursive function or table. The recursive solution will invoke redundant computation in C(m-1, n-1). So using a DP table (array) can simplify the computation and finish in O(m x n) time. The storage is O(m) or O(n).

[Solution]:

// non-recursive, Java
public class Solution {

public int uniquePaths(int m, int n) {
    if ( m>100 || n>100) return -1;
    int[] arr = new int[m];

    for (int i=0; i<m; i++) arr[i]=1;
    for (int j=1; j<n; j++) {
        for (int i=1; i<m; i++) {
             arr[i] += arr[i-1];
        }
     }

     return arr[m-1];
}
}

[Variation]:

If there are obstacles in the matrix, how to calculate the paths? Suppose there is a obstacle grid.

[Analysis]:
C(m, n) = 0 if there is an obstacle in grid(m, n).

[Solution]:
//C++
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        vector<int> count (obstacleGrid.size(),0);
        for (int i=0; i<obstacleGrid.size(); i++) {
            if (obstacleGrid[i][0] == 0) count[i] = 1;
            else break;
        }
        
        for (int j=1; j<obstacleGrid[0].size(); j++) {
            if (obstacleGrid[0][j]==1) count[0] = 0;    //tricky
            for (int i=1; i<obstacleGrid.size(); i++) {
                if (obstacleGrid[i][j]==1) count[i] = 0;
                else count[i] +=count[i-1];
            }
        }
        
        return count.back();
    }
};