# Java 3 solutions: Recursion, Memoization, DP

1. Plain recursion
``````class Solution {
int[][] matrix;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {

matrix = obstacleGrid;

if(matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] ==  1) {
return 0;
}
return paths(matrix.length-1, matrix[0].length-1);

}

private int paths(int m, int n){

if(m == 0 && n == 0) return 1;

if(m<0 || n<0 || matrix[m][n] == 1) return 0;

return paths(m-1,n)+paths(m,n-1);

}
}

``````
1. Memoization
``````class Solution {
int[][] matrix;
Map<String, Integer> cache;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {

matrix = obstacleGrid;
cache = new HashMap<String, Integer>();

if(matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] ==  1) {
return 0;
}
return paths(matrix.length-1, matrix[0].length-1);

}

private int paths(int m, int n){
String str = m + "," + n;

if(cache.containsKey(str)){
return cache.get(str);
}

if(m == 0 && n == 0) return 1;

if(m<0 || n<0 || matrix[m][n] == 1) return 0;

cache.put(str, paths(m-1,n)+paths(m,n-1));

return cache.get(str);
}
}

``````
1. DP
``````class Solution {

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

if(obstacleGrid.length==0 || obstacleGrid[0].length==0 ) {
return 0;
}

int m=obstacleGrid.length;
int n=obstacleGrid[0].length;

int dp[][] = new int[m][n];

if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1) {
return 0;
}

dp[0][0]=1;

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

if (obstacleGrid[i][0]==1) {
dp[i][0]=0;
} else {
dp[i][0]=dp[i-1][0];
}
}

for(int j=1; j<n; j++){

if(obstacleGrid[0][j]==1) {
dp[0][j]=0;
}
else {
dp[0][j]=dp[0][j-1];
}
}

for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {

if(obstacleGrid[i][j]==1) {
dp[i][j]=0;
}
else {
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}

return dp[m-1][n-1];
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.