# 45. Jump Game 2 跳跃游戏2

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

``````int jump(vector<int>& nums) {
int res = 0;       // 记录跳d了几次
int size = nums.size();
if (size<2) return 0;
for (int i = 0; i < size; ) {
int steps = nums[i]; // 第i个元素可以走的步数
int max = 0;
int step = 0;        // 第i个元素实际走的步数
while (steps > 0) {
// 如果这一步跳出超过边界,直接返回
if (i + steps >= (size-1)) {
res ++;
return res;
}else{
// 保存最远到达
int tmp = nums[i+steps]+(i+steps);
if (tmp > max){
max = tmp;
step = steps;
}
steps--;
}
}
if (step > 0) {
res ++;
i += step;
if (i>=(size-1))
return res;
}else{
return 0;
}
}
return 0;
}
``````

``````int jump2(vector<int>& nums) {
// last为上一次到达的最远值
int res = 0, n = nums.size(), last = 0, cur = 0;
for (int i = 0; i < n - 1; ++i) {
// 记录当前能到达的最远值
cur = max(cur, i + nums[i]);
// 当i到达last的时候,说明结束了上一个最大范围,需要加1
if (i == last) {
last = cur;
++res;
if (cur >= n - 1) break;
}
}
return res;
}
``````