Leetcode 55: Jump Game (recursive+memo)

leetcode_55b.cpp

#include <iostream>
#include <vector>

using namespace std;

// This recursive leetcode 55 solution times out on some the leetcode test cases

bool walk(const vector<int>& nums, int idx, vector<bool>& dp) {
    if (idx == nums.size()-1) return true;
    if (dp[idx]) return false;
    
    int i = idx + nums[idx];  //start from biggest step
    if  (i >= nums.size()) i = nums.size()-1; //truncate if past end
    for ( ; i > idx; --i) {
        if (walk(nums, i, dp)) return true;
    }
    dp[idx] = true;
    return false;
}

bool canJump(vector<int>& nums) {
    vector<bool> dp(nums.size(), false);
    return walk(nums, 0, dp);
}

int main() {
    vector<int> nums {2,3,1,1,0}; //{3,2,1,0,4}; //{2,3,1,1,0}; //{2,3,1,1,4};
    cout << canJump(nums) << "\n";
    return 0;
}