Who can tell me why my code is TLE?


  • 1
    B

    I use a cache named dp in my code for the visited pair(m,n)
    using dfs method.
    but got TLE. here is my code:

    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	int m=obstacleGrid.length;
    	int n=obstacleGrid[0].length;
    	if(obstacleGrid[0][0]==1|| obstacleGrid[m-1][n-1]==1)	return 0;
    	int[][] dp=new int[m+1][n+1];
    	dp[m-1][n-1]=1;
    	return dfs(obstacleGrid,0,0,m,n,dp);
    	
    }
    
    private int dfs(int[][] obstacleGrid, int i, int j, int m, int n,int[][] dp) {
    	// TODO Auto-generated method stub
    	if(i>=m || j>=n)	return 0;
    	if(dp[i][j]>0)	return dp[i][j];
    	if(obstacleGrid[i][j]==1)	return 0;
    	dp[i][j]=dfs(obstacleGrid,i+1,j,m,n,dp)+dfs(obstacleGrid,i,j+1,m,n,dp);
    	return dp[i][j];		
    }
    

    }

    what confused me is the code below is Accepted!!

    public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	int m=obstacleGrid.length;
    	int n=obstacleGrid[0].length;
    	if(obstacleGrid[0][0]==1|| obstacleGrid[m-1][n-1]==1)	return 0;
    	int[][] dp=new int[m+1][n+1];
    	dp[0][0]=1;
    	return dfs(obstacleGrid,m-1,n-1,m,n,dp);
    	
    }
    
    private int dfs(int[][] obstacleGrid, int i, int j, int m, int n,int[][] dp) {
    	// TODO Auto-generated method stub
    	if(i<0 || j<0)	return 0;
    	if(dp[i][j]>0)	return dp[i][j];
    	if(obstacleGrid[i][j]==1)	return 0;
    	dp[i][j]=dfs(obstacleGrid,i-1,j,m,n,dp)+dfs(obstacleGrid,i,j-1,m,n,dp);
    	return dp[i][j];		
    }
    

    }


  • -1
    L

    The first solution is literally wrong, where the following formulas does not hold.

    dp[i][j]=dfs(obstacleGrid,i+1,j,m,n,dp)+dfs(obstacleGrid,i,j+1,m,n,dp);
    

    It should be the one in the second solution.

    dp[i][j]=dfs(obstacleGrid,i-1,j,m,n,dp)+dfs(obstacleGrid,i,j-1,m,n,dp);
    

    By the way, it does not seem to be a good idea to using recursion to solve this problem. It is like calculating fibonacci in a recursive way, it is correct, but the complexity is exponential, and one could totally solve it in sort of dynamic programming way in linear complexity.


  • 0
    R

    The problem with your solution is that if the goal is unreachable from a cell [i][j], then dp[i][j] is set to 0 which means that next time you need to get a value for [i][j] you'll need to recalculate it again. This happens because 0 is not a special value and it can mean two things: the goal is not reachable from the cell or the value is not calculated yet.

    A possible fix is to assign a special value (e.g. -1) to dp[i][j] if the goal is not reachable from [i][j]:

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1|| obstacleGrid[m-1][n-1]==1)   return 0;
        int[][] dp=new int[m+1][n+1];
        dp[m-1][n-1]=1;
        return dfs(obstacleGrid,0,0,m,n,dp);
    
    }
    
    private int dfs(int[][] obstacleGrid, int i, int j, int m, int n,int[][] dp) {
        // TODO Auto-generated method stub
        if(i>=m || j>=n)    return 0;
        if(dp[i][j]>0)  return dp[i][j];
        if(obstacleGrid[i][j]==1 || dp[i][j]== -1)   return 0;
        dp[i][j]=dfs(obstacleGrid,i+1,j,m,n,dp)+dfs(obstacleGrid,i,j+1,m,n,dp);
        if (dp[i][j] == 0) {
            dp[i][j] = -1;
        }
        return (dp[i][j]==-1)?0:dp[i][j];        
    }

Log in to reply
 

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