time limit exceeded


  • 0
    L


    int uniquePaths(int m, int n) {
    if (m == 1 && n == 1) return 1;
    else if (m == 1 && n > 1) return uniquePaths(m, n-1);
    else if (m > 1 && n == 1) return uniquePaths(m-1, n);
    else if (m > 1 && n > 1) return uniquePaths(m, n-1) + uniquePaths(m-1, n);
    }


  • 0

    Hi @lakeat, thanks for sharing your solution. I found that a recursive solution will be accepted if a memo is used to track the previously calculated path counts, since there are a significant amount of overlapping sub-problems...

    class SolutionRC {
    public:
        int uniquePaths(int m, int n) {
            map<pair<int,int>,int> memo{};
            return helper(m,n,0,0,memo);
        }
    private:
        int helper(const int& m, const int& n, int i, int j, map<pair<int,int>,int>& memo){
            if (memo.find({i,j})!=memo.end()) return memo[{i,j}];
            if (i==m-1 || j==n-1) return memo[{i,j}]=1;
            return memo[{i,j}]=helper(m,n,i+1,j,memo)+helper(m,n,i,j+1,memo);
        }
    };
    

Log in to reply
 

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