# What is wrong with my recursive solution?

• ``````public int minPathSum(int[][] grid) {
if(grid==null) return 0;

int m=grid.length, n=grid[0].length;
return minPath(grid,m-1,n-1);
}

public int minPath(int[][] grid, int m, int n){
if(m==0&&n==0) return grid[0][0];
if(m==0) return grid[0][n] + minPath(grid, 0, n-1);
if(n==0) return grid[m][0] + minPath(grid,m-1,0);

return grid[m][n] + Math.min(minPath(grid,m-1,n), minPath(grid,m,n-1));
}
``````

Here is my code. One big test case didn't go through. It says Time Limit Exceeded.

• For this problem, you need to use dynamic programming, as opposed to a naive recursive solution, otherwise it is almost impossible to pass large test cases.

• For you reference...I think store some recursion function may be useful..

``````public int minPathSum(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
boolean[][] visited=new boolean[m][n];
int[][] result=new int[m][n];
return minPathSum(grid, 0,0, result, visited);
}

public int minPathSum(int[][] grid, int x, int y, int[][] result,boolean[][] visited){
if(visited[x][y]){
return result[x][y];
}
int m=grid.length;
int n=grid[0].length;
if(x==m-1 && y==n-1) {
visited[x][y]=true;
result[x][y]=grid[m-1][n-1];
return grid[m-1][n-1];
}else if(x==m-1 && y<n-1) {
int current=minPathSum(grid,x,y+1,result,visited)+grid[x][y];
visited[x][y]=true;
result[x][y]=current;
return current;

}else if(x<m-1 && y==n-1){
int current= minPathSum(grid,x+1,y,result,visited)+grid[x][y];
visited[x][y]=true;
result[x][y]=current;
return current;
}else{
int current=Math.min(minPathSum(grid,x+1,y,result,visited),minPathSum(grid,x,y+1,result,visited))+grid[x][y];
visited[x][y]=true;
result[x][y]=current;
return current;
}
}
``````

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• IMO , the following LOC can be used
if(m==0) return grid[0][n] ;
if(n==0) return grid[m][0] ;