[HELP!!] C++ Recursive Method, but why TLE?


  • 0
    I

    C++ Recursive Method, but why TLE?

    
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            if(m == 0 || n == 0){
                return 0;
            }
            return startpoint(1, 1, m, n);
        }
        
        int startpoint(int x, int y, int m, int n) {
            if(x > n || y > m){
                return 0;
            }
            
            if(x == n && y == m){
                return 1;
            }
            
            return startpoint(x + 1, y, m ,n) + startpoint(x, y + 1, m, n);
        }
    };
    
    

    I try and failed at m = 23, n = 12

    could any one tell me why and how to solve?


  • 0

    At every position you have 2 branches, so I think naive recursion is actually exponential, O(2^(M+N)).

    To estimate very roughly, in your case, M+N = 34, since you start from 1, 1 so it is really 32, 2^32, which is about 4 * 10^9, which requires at least 4 Gig of CPU cycles, and in the real world it is more than that, so you are TLE.

    Notice that in the search tree, a lot of nodes are searched multiple times, you can see this by printing out x and y in startpoint and try to run the program.
    In this case, we can easily speed up the search by storing intermediate results, so next time startpoint is called on a calculated x, y, it won't repeat itself. For this problem you can use a 2D array or hashtable (unordered_map in C++) to store intermediate results. There are really only m*n nodes to call startpoint on, and by storing results, calling startpoint will only cost O(1) in time, and the whole algorithm will be optimized to O(MN) in time with O(MN) extra space. And O(MN) << O(2^(M+N))


  • 0
    F

    You code run time is O(2^(m+n)),You will need to use memorization to optimize the run time to O(m*n).

     int startpoint(int x, int y, int m, int n, vector<vector<int>> & cache) {
            if(x > n || y > m){
                return 0;
            }
            
            if(x == n && y == m){
                return 1;
            }
            if (cache[x][y] != -1) return cache[x][y];
            return cache[x][y] = startpoint(x + 1, y, m ,n, cache) + startpoint(x, y + 1, m, n, cache);
        }
    

  • 0
    H

    Hi,

    Recursive is correct, but you should grab an algorithm book to see when you need to do dynamic programming (recursive resolves big problems by resolving more sub-problems. But when there're overlapping sub-problems, too much time is wasted on those sub-problems. So that's dynamic programming - don't calculate every time, calculate once and store the value. If next time the same sub-problem needs to be solved, return the value directly).


Log in to reply
 

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