My recursive code got TLE


  • 0
    H

    My idea is simple. I use 'i' and 'j' to keep the current position, and use 'sum' to keep the current path sum. The 'localmin' is used to keep the minimum HP needed for each path. The 'globmin' is a global variable that is used to keep the minimum HP needed among all paths.
    The code cannot pass the test case of a large input 2D matrix. I think the logic is quite similar to the DP solution, so the time complexity is also O(m*n). I know I should always use a non-recursive code if I can because it takes more memory, but can anyone tell me why this gets a TLE?

    class Solution {
     public:
    	 int globmin = INT_MAX;
    	 int w;
    	 int h;
    
    	 int calculateMinimumHP(vector<vector<int> > &dungeon) {
    	     w = dungeon[0].size();
    	     h = dungeon.size();
    		 recurRun(dungeon, 0, 0, 0, INT_MIN);
    		 return globmin;
    	 }
    
    	 void recurRun(vector<vector<int>>& dungeon, int i, int j, int sum, int localmin) {
    		 if (i >= w || j >= h) return;
    		 
    		 int currSum = sum + dungeon[j][i];
    		 localmin = max(localmin, (currSum <= 0 ? -currSum + 1 : 0));
    		 
    		 if (i == w - 1 && j == h - 1) { // reach princess, update the globmin
    			 globmin = min(localmin, globmin);
    			 return;
    		 }
    
    
    		 if (localmin >= globmin) return; // accelerate
    		 
    		 // choose right
    		 recurRun(dungeon, i + 1, j, currSum, localmin);
    		 // choose down
    		 recurRun(dungeon, i, j + 1, currSum, localmin);
    	 }
     };

  • 1
    C

    The naive recursive algorithm easily introduces a lot of repeated computation. Try drawing the recursion tree on a whiteboard and you will find our why.

    DP is fast because it stores the computed values. Your recursive algorithm can also be improved by caching the computed values in a hash table. In the beginning of this function, if you find this cell has been processed just simply return the stored value.


  • 0
    H

    The solution it provided compute every possibility only once. And it stores the data as local value in the function. I still don't understand why TLE is happening.


  • 0
    H

    Thanks. I think I know the reason. Mine is actually a backtrack code instead of a recursive code as I thought, so I repeatedly process a single position for many times without saving any intermediate results.

    Here is the modified code using recursion.

    class Solution {
    private:
    int w;
    int h;
    unordered_map<int, int> proccessedPosition;
    
    public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        h = dungeon.size();
        if (h==0) return 0;
        w = dungeon[0].size();
        if (w==0) return 0;
        
        return recur(dungeon, 0, 0);
    }
    
    int recur(vector<vector<int>>& dungeon, int i, int j) {
        /// assert(i<w && j<h);
        if (proccessedPosition.count(i+j*w) > 0) return proccessedPosition[i+j*w];
        
        if (i==w-1 && j==h-1) {
            return dungeon[j][i] >= 0 ? 1:1-dungeon[j][i];
        }
        
        int right = INT_MAX, left = INT_MAX;
        if (i+1 < w) {
            right = recur(dungeon, i+1, j);
        }
        
        if (j+1 < h) {
            left = recur(dungeon, i, j+1);
        }
        
        int minnext = min(right, left);
        int currHP  = dungeon[j][i]>=0?1:1-dungeon[j][i];
        
        proccessedPosition[i+j*w] = max(currHP, minnext-dungeon[j][i]);
        return proccessedPosition[i+j*w];
    }
    

    };


Log in to reply
 

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