Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 45: Jump Game II (iterative DP O(n^2) time)
//This is too slow for some of the leetcode test cases. Just posting for reference
#include <iostream>
#include <vector>
using namespace std;
int jump(vector<int>& nums) {
if (nums.size()==0) return 0;
vector<int> dp(nums.size(), -1);
int n = nums.size();
dp[0] = 0;
for (int i=1; i<n; ++i) { //calculate dp (minimum jumps) at each position
int minSteps = INT_MAX;
for (int j=0; j<i; ++j) { //calculate minSteps from each previous dp position
if (nums[j] < i-j) continue; //not possible to get to current from this previous
minSteps = min(minSteps, dp[j]+1);
}
dp[i] = minSteps;
}
return dp[n-1];
}
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