Leetcode 45: Jump Game II (iterative DP O(n^2) time)

leetcode_45b.cpp

//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;
}