# Who can tell me why my code is TLE?

• 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];
}
``````

}

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

• 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];
}``````

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