```
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.empty()) return -1;
int N = nums.size(),lastFarthest=0;
vector<int> dp(N,N+1);
dp[0]=0;
for(int i=0;i<N-1;i++){
int cover_length = nums[i];//cover range:i ~ i+cover_length;
if(i+cover_length <=lastFarthest) continue; //pruning
if(i+cover_length >=N-1)
return 1+dp[i]; //pruning
for(int j=lastFarthest+1;j<=i+cover_length && j<N;j++){
dp[j] = 1+dp[i];
}
lastFarthest = i+cover_length;
}
return dp[N-1];
}
};
//nums:[2,3,1,1,4,1,2,3,1,2,1 ,2 ,1 ,3]
//dp: [0,1,1,2,2,3,3,3,3,4,4 ,5, 6 ,6]
```