[Path][DP] Unique Paths II

1. Example

[
[0 ,0 ,0]
[0 ,1, 0]
[0 ,0, 0]
]
return the total number of unique paths is 2



2. Implementation
res[j] = res[j] + res[j-1];
res[j] = 0 if grid is 1
[1,1,1]
[1,X,1]
[1,1, 2]
DP
1. prev info
2. iterate
3. init value

// Time:(m*n) for for loop, Space:O(n) array
public int uniquePAthsWithObstacles(int[][] obstacleGrid)
{


       // validate the input
       if ( obstacleGrid == null || obstacleGrid.length == 0|| obstacle[0].length ==0 )
       {
            return 0;
       }




       int[] res = new int[obstacleGrid[0].length];
       res[0] = 1;
       //if (obstacleGrid[0][0] != 0) never happen
       for (int i = 0 ; i < obstacleGrid.length; i++)
       {
           for ( int j = 1 ; j < obstacleGrid[0].length;j++) 
           {
               res[j] = (obstacleGrid[i][j] == 0)?res[j]+res[j-1]:0;
           }
       }





       return res[obstacleGrid[0].length-1];
}

// Time:O(m*n) go over all cells, Space:O(n)
public int uniquePath(int[][] obstacleGrid)
{
      // validate the input
      if ( obstacleGrid == null || obstacleGrid.length == 0 || obstacle[0].length == 0)
      { 
           return 0;
      }
      
     
      return helper(obstacleGrid, 1,1);

}
private int helper(int[][] grid, int m, int n)
{



      if ( m == grid.length && n == grid[0].length)
      {
           return 1;
      }
      if (m > grid.length || n > grid[0].length)
      {
          return 0;
      }
      if ( grid[m][n] == 1 )
      {
          return 0;
      }



      helper(grid, m+1, n) + helper(grid, m, n+1);
}
   123

1  000
2  010
3  000

m = 3 and n = 3
(1,1)
     (2,1)        +              (1,2)
     (3,1)        + (2,2)X       (2,2)X           +  (1,3)
     (4,1)X+(3,2)                                    (2,3) + (1,4)X
            (4,2)X+(3,3)                             (3,3) + (2,4)X 
record when base case happen 
(1,1)(2,1)(3,1)(3,2)(3,3)
(1,1)(1,2)(1,3)(2,3)(3,3)

3. Similar Ones
Unique Paths