public class Solution {

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

int[][] dpGrid = new int[obstacleGrid.length][obstacleGrid[0].length];
for(int[] i : dpGrid)
{
Arrays.fill(i, -1);
}
if(obstacleGrid[obstacleGrid.length -1][obstacleGrid[0].length -1] == 1)
{
return 0;
}
return getAllPaths(obstacleGrid, dpGrid, obstacleGrid.length - 1, obstacleGrid[0].length - 1);
}
public int getAllPaths(int[][] grid,int[][] dpGrid, int m, int n)
{
if(m == 0 && n == 0)
{
if(grid[m][n] == 0)
{
return 1;
}
else
{
return 0;
}
}
else if(m < 0 || n < 0)
{
return 0;
}else if(dpGrid[m][n] != -1)
{
return dpGrid[m][n];
}
else if(m == 0)
{
if(grid[m][n - 1] == 0)
{
dpGrid[m][n] = getAllPaths(grid, dpGrid, m, n - 1);
return dpGrid[m][n];
}else{
dpGrid[m][n] = 0;
return dpGrid[m][n];
}
}
else if(n == 0)
{
if(grid[m -1][n] == 0)
{
dpGrid[m][n] =getAllPaths(grid, dpGrid, m - 1, n);
return dpGrid[m][n];
}else{
dpGrid[m][n] = 0;
return dpGrid[m][n];
}
}
else{
if(grid[m - 1][n] == 0 && grid[m][n - 1] == 0)
{
dpGrid[m][n] = getAllPaths(grid,dpGrid, m -1, n) + getAllPaths(grid, dpGrid, m, n - 1);
return (dpGrid[m][n]);
}else if(grid[m - 1][n] == 1 && grid[m][n - 1] == 0)
{
dpGrid[m][n] = getAllPaths(grid, dpGrid, m, n - 1);
return 1 * (dpGrid[m][n]);
}else if(grid[m - 1][n] == 0 && grid[m][n - 1] == 1)
{
dpGrid[m][n] = getAllPaths(grid, dpGrid, m -1 , n);
return 1 * (dpGrid[m][n]);
}
else
{
dpGrid[m][n] = 0;
return dpGrid[m][n];
}
}
}

}