@[toc]
题目
Problem: 45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]
题解
思路
正向太复杂，直接考虑反向，从后往前跳。
每次都试图跳到最前面，重复多次，到达起点即可。
试图跳到最前面的原因：
如果有两种路线可以跳到n-1位置，一个从j出发，一个从k出发，j<k，那么，前一次跳跃：
- 如果从j的前方出发，能够到达k的跳跃一定能到达j，而能够到达j的跳跃不一定能到达k，可能需要再一次跳跃，所以选择j，这话次数不会比k多。
- 如果从j的后方出发，可以将新的出发点视为k，增加了一次跳跃，但情况没有任何改善。
解题方法
- 定义一个函数，输入现在的位置，输出跳到现在位置的最优起点（即index最小的起点）
采用一个遍历，从0开始往后遍历，直到能够到达现在的位置，就返回，如果没找到，返回NAN
- 采用一个while循环，当位置>0时，重复调用1中的函数，并计数。
复杂度
时间复杂度:
空间复杂度:
Code
class Solution {
public:
int jump(vector<int>& nums) {
//只要弹跳最大长度比所需要的长度长，那么就可以弹跳。
//我们需要找到弹跳次数的最小值，如果某种情况确定比其他情况更快，即可以将其他情况排除。
//从正向来分析的话，可能性有非常多种，因为弹跳时可以在最大长度以内随意跳跃，不知道哪一个是最优解。
//只能从反向来分析，如果我需要跳跃到末尾，可能性是相对有限的，它所在的位置+它的值高于末尾所在的位置才可以跳跃。
//最重要的特性：在一步弹跳内，出发的位置越靠前，一定越有优势，因为在一次跳跃中，能跳到靠后位置的，一定能跳到靠前的位置，但能跳到靠前位置的，可能需要再一次跳跃才能跳到靠后的位置，因此，靠前的出发点不会比靠后的出发点所需要的次数更多。
//以下所有内容，采用反向的分析，即从末尾往前跳，每次跳到可行的最远的位置
int place = nums.size()-1;
auto oneJump = [&](int placeBefore)->int{//一次jump（从后往前跳），输入jump前的place，输出jump后的place，输出的place是所有jump可能中，最靠前的那一个jump
for(int i = 0; i<placeBefore;i++){//从前开始遍历，遍历到能够到达placeBefore即返回
if(nums[i] + i >= placeBefore){
return i;
}
}
return NAN;
};
int jumpTime = 0;
while(place > 0){
place = oneJump(place);
jumpTime++;
}
return jumpTime;
};
};
