Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 45: Jump Game II (recursive+memo)
//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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment