Please help me with the TLE issue


  • 1
    A

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

  • 4
    B

    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).
    Using some cache can help you reduce the time significantly.


Log in to reply
 

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