Why does this DP solution give TLE?


  • 0
    T

    Why does this DP solution give TLE? Please advice.

    class Solution {
    public:
        unordered_map<int,bool> dp;
        
        bool helper(vector<int>& nums, int currentIdx) {
            if (currentIdx >= nums.size()) {
                return false;
            }
            
            if (currentIdx == nums.size()-1) {
                return true;
            }
            
            if (dp.find(currentIdx) != dp.end()) {
                return dp[currentIdx];
            }
            
            bool retval = false;
            int current = nums[currentIdx];
            for (int j=current; j>=1; --j) {
                if (helper(nums, currentIdx+j)) {
                    retval = true;
                    break;
                }
            }
            
            dp[currentIdx] = retval;
            return retval;
        }
    
        bool canJump(vector<int>& nums) {
            if (nums.empty()) {
                return false;
            }
            cout << "size: " << nums.size() << "\n";
            dp.clear();
            return helper(nums, 0);
        }
    };
    

Log in to reply
 

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