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.

 1 public class Solution { 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) { 3         int m = obstacleGrid.length; 4         int n = obstacleGrid[0].length; 5         if (m == 0 || n == 0) return 0;  6         if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0; 7         int[][] matrix = new int[m][n]; 8         return FindPath(m-1, n-1, obstacleGrid, matrix); 9     }10     11     public int FindPath(int i, int j, int[][] obstacleGrid, int[][] matrix) {12         if (matrix[i][j] != 0) return matrix[i][j];13         if (i == 0 && j == 0) return 1;14         if (i == 0 && j != 0 && obstacleGrid[i][j] != 1) {15             matrix[i][j] = FindPath(i, j-1, obstacleGrid, matrix);16             return matrix[i][j];17         }18         if (i != 0 && j == 0 && obstacleGrid[i][j] != 1) {19             matrix[i][j] = FindPath(i-1, j, obstacleGrid, matrix);20             return matrix[i][j];21         }22         if (i != 0 && j != 0 && obstacleGrid[i][j] != 1) {23             matrix[i][j] = FindPath(i, j-1, obstacleGrid, matrix) + FindPath(i-1, j, obstacleGrid, matrix);24             return matrix[i][j];25         }26         else return 0;27     }28 }