# Java 3 solutions: Recursion, Memoization, DP

1. Plain Recursion
``````class Solution {

int[][] matrix;

public int minPathSum(int[][] grid) {
matrix = grid;

if(grid.length == 0 || grid[0].length == 0) return 0;

return path(0,0);

}

private int path(int i, int j) {

if(i==matrix.length-1 && j==matrix[0].length-1){
return matrix[i][j];
}

if(i >= matrix.length || j >= matrix[0].length) {
return Integer.MAX_VALUE;
}

return Math.min(path(i+1,j), path(i,j+1)) + matrix[i][j];

}
}

``````
1. Memoization
``````class Solution {

int[][] matrix;
Map<String, Integer> cache;

public int minPathSum(int[][] grid) {
matrix = grid;
cache = new HashMap<String, Integer>();
if(grid.length == 0 || grid[0].length == 0) return 0;

return path(0,0);

}

private int path(int i, int j) {

String str = i+","+j;

if(i==matrix.length-1 && j==matrix[0].length-1){
return matrix[i][j];
}

if(i >= matrix.length || j >= matrix[0].length) {
return Integer.MAX_VALUE;
}

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

int l=Integer.MAX_VALUE; int r = Integer.MAX_VALUE;

l = path(i+1, j);
r = path(i, j+1);

cache.put(str, Math.min(l,r) + matrix[i][j]);

return cache.get(str);

}
}
``````
1. DP
``````class Solution {
public int minPathSum(int[][] grid) {

if(grid.length == 0 || grid[0].length == 0) return 0;

int[][] dp = new int[grid.length][grid[0].length];

dp[0][0] = grid[0][0];

for(int i=1; i<grid.length; i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}

for(int j=1; j<grid[0].length; j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}

for(int i=1; i<grid.length; i++) {

for(int j=1; j<grid[0].length; j++){

dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j];

}

}

return dp[grid.length-1][grid[0].length-1];

}
}

``````

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