Leetcode 45: Jump Game II (recursive+memo)

leetcode_45a.cpp

//This is too slow for some of the leetcode test cases. Just posting for reference
#include <iostream>
#include <vector>

using namespace std;

int walk(const vector<int>& nums, int idx, vector<int>& dp) {
    if (idx >= nums.size()) return 0;
    if (dp[idx] != -1) return dp[idx];
    if (idx == nums.size()-1) { dp[idx]=0; return 0; }

    int minSteps = INT_MAX;
    int initial = min(idx+nums[idx], int(nums.size()-1));
    for (int i=initial; i>idx; --i) {
        if (i >= nums.size()) continue;
        int steps = walk(nums, i, dp);
        if (steps == INT_MAX) continue;  //dead end
        minSteps = min(minSteps, steps+1);
    }
    dp[idx] = minSteps;
    return minSteps;
}

int jump(vector<int>& nums) {
    vector<int> dp (nums.size(), -1);
    return walk(nums, 0, dp);
}

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