Why is my recursive method has TLE problem, please help!


  • 0
    X
    Below is my code. I use DP and recursive method. 
    Start from (0,0) to (m, n). And store the number of paths from each of the point to the destination in an array. Is there anything i can do to overcome the TLE problem?
    
    public int uniquePathsWithObstacles(int[][] grid) {
            if(grid==null) return 0;
            int m=grid.length, n=grid[0].length;
            int[][] w=new int[m][n];
            find(grid, w, 0, 0);
            return w[0][0];
        }
        
        public int find(int[][] grid, int[][] w, int m, int n){
            int row=grid.length, col=grid[0].length;
            if(m>=row||n>=col) return 0;
            if(w[m][n]>0||grid[m][n]==1) return w[m][n];
            if(m==row-1&&n==col-1) w[m][n]=1;
    
            if(m<row-1) w[m][n]+=find(grid, w, m+1, n);
            if(n<col-1) w[m][n]+=find(grid, w, m, n+1);
            return w[m][n];
        }

  • 2
    R

    I don't think a recursive solution could be DP.

    here is my solution in java

    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int array[] = new int[obstacleGrid[0].length+1];
        array[1]=1;
    
        for (int i=0;i<obstacleGrid.length;i++)
            for (int j=1;j<=obstacleGrid[0].length;j++)
                if (obstacleGrid[i][j-1]==0)
                    array[j]+=array[j-1];
                else array[j]=0;
                
        return array[obstacleGrid[0].length];
        
    }
    

    }


  • 0
    X

    Thanks for your code. I think DP means for the questions when we use divide and conquer, we find out that some of the sub problems overlap, so we want to use a table to store the results of this overlap sub problems and do not recalculate them again. It doesnt matter if the program is recursive or iterative.


  • 0
    R

    You are absolutely right about the definition of DP. However, recursion is intrinsically against the nature of DP since it is unable to handle overlaps. Taking your code, I am not pretty sure I understand every line but I am confident about your core algorithm. In you @{code find()}, suppose the computer is calculating the value of m[2][2], so it needs the value of m[3][2] & m[2][3]. When calculating the value of m[1][3], m[2][3] will be used again. So there is a overlap. If you draw a recursive tree, it will be more explicit to understand.


  • 0
    S

    "recursion is intrinsically against the nature of DP since it is unable to handle overlaps" Not necessarily. For many problems, recursion + memoization would already result in an optimal DP solution (Top-down DP). The 'table-filling' way (Bottom-up DP) is usually more memory efficient and avoids the overheads of recursive function calls, but it doesn't mean that it is the only way DP is supposed be implemented.


  • 0
    S

    Your code is theoretically correct and indeed has the same theoretical running time as the iterative DP. What caused the TLE could be the overhead introduced by the function calls and extra stack space consumed, as well as other operations that you could have done only once. For instance, I really see no point of calculating 'row' and 'col' every time 'find' is called since the size of the grid never changes, and 'if(m==row-1&&n==col-1) w[m][n]=1;' should not in the recursive function as well.

    For reference, I just implemented your idea (although not identically) in C++. It is three times as slow as the iterative version, but it can surely gets accepted:

    vector<vector<int> > w;
    int nr, nc;
    
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        nr = obstacleGrid.size(); if (nr == 0) return 0;
        nc = obstacleGrid[0].size(); if (nc == 0) return 0;
        w = vector<vector<int> >(nr, vector<int>(nc, 0));
        w[0][0] = (obstacleGrid[0][0] != 1);
        return find(obstacleGrid, nr-1, nc-1);
    }
    
    int find(vector<vector<int> >& grid, int r, int c)
    {
        if (r < 0 || c < 0) return 0;
        if (w[r][c] != 0 || grid[r][c] == 1) return w[r][c];
        w[r][c] = find(grid, r-1, c) + find(grid, r, c-1);
    }
    

    This code is not so much different from yours, but it has fewer if-clauses and temporary variables. Instead of finding w[0][0], I changed it to w[nr-1][nc-1], so that in every function call, you only need to compare r and c with 0, as opposed to row and col. I believe your code in java can be accepted as well if said optimizations are made.


  • 0
    R

    I implemented your solution in java. Can you answer some question in my following thread?


  • 0
    R

    Sterali's solution in JAVA

    public class Solution {
    int [][] w;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int nr=obstacleGrid.length;
        if (nr==0 ) return 0;
        int nc=obstacleGrid[0].length;
        if (nc == 0) return 0;
        w = new int[nr][nc];
        w[0][0]=(obstacleGrid[0][0]!=1)?1:0;
        return find (obstacleGrid,nr-1,nc-1);
    }
    int find(int[][] grid,int r,int c){
    if (r < 0 || c < 0) 
        return 0;
    if (w[r][c] != 0 || grid[r][c] == 1) //Why return w[r][c] when w[r][c]!=0?
        return w[r][c];
    return w[r][c] = find(grid, r-1, c) + find(grid, r, c-1);
    }
    

    }


  • 0
    R

    Why return w[r][c] when w[r][c]!=0?
    Sounds like I got your point. It do avoid the overlap.


  • 0
    S

    Because all elements in w are initialized to 0, so if any element is not equal to 0 at any point, it means it had already been computed so there is no need to recompute it anymore.


Log in to reply
 

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