• Hi. I just coded this problem in a recursive DP method. I have realized that it costed a lot of time through many calls of the recursive functions, so my implementation is never fast enough. Anyway, I think it is still approximately of complexity of O(n^2).

Could anyone help me with the TLE issue? Thanks a lot.

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
if (m <= 0) {
return 0;
}
int n = obstacleGrid[0].size();
if (n <= 0) {
return 0;
}
vector< vector<int> > path_num(m, vector<int>(n, 0));

if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
return 0;
}

return UniquePathsWithObstacles(obstacleGrid, 0, 0, m, n, path_num);
}

int UniquePathsWithObstacles(const vector< vector<int> >& obstacleGrid, int i, int j, int m, int n, vector< vector<int> >& path_num) {
int right = 0;
int below = 0;

if (path_num[i][j] != 0 || obstacleGrid[i][j] == 1) {
return path_num[i][j];
}

if (j < n - 1 && obstacleGrid[i][j + 1] == 0) {
right = UniquePathsWithObstacles(obstacleGrid, i, j + 1, m, n, path_num);
}
if (i < m - 1 && obstacleGrid[i + 1][j] == 0) {
below = UniquePathsWithObstacles(obstacleGrid, i + 1, j, m, n, path_num);
}
if (i == m - 1 && j == n - 1) {
path_num[i][j] = 1;
return 1;
} else {
path_num[i][j] = right + below;
return right + below;
}
}
};

• Most of the points are calculate more than once.
For example, you calculate (3, 2) and (2, 3) to get (2, 2), but you also calculate (3,2) to get (3,1) and calculate (2, 3) to get (1, 3).