What is wrong with my recursive solution?


  • 0
    S
    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.


  • 0
    S

    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.


  • 0
    S

    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;
        }
    }
    

  • 0
    S

    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


  • 0
    I

    IMO , the following LOC can be used
    if(m==0) return grid[0][n] ;
    if(n==0) return grid[m][0] ;
    instead of
    if(m==0) return grid[0][n] + minPath(grid, 0, n-1);
    if(n==0) return grid[m][0] + minPath(grid,m-1,0);


Log in to reply
 

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