跳跃游戏
一个下标对应的值为3，那证明这个位置可以跳到前后3个位置的下标处。（±3均可达）
如果依次遍历完这个数组，有下标在跳跃过程中最远位置仍然不可达，即证明无法到达最后一个位置。
可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
如果可以一直跳到最后，就成功了
class Solution { public: bool canJump(vector<int>& nums) { // vector<int> res() int length = nums.size()-1; if(length == 0) return true; int max_index = 0; for(int i = 0;i < length;i++) { if(max_index < i) return false;; max_index = max(nums[i]+i,max_index); if(max_index >= length) return true; } return false; } };
跳跃游戏Ⅱ
分析跳跃到最远位置会依赖于之前跳跃的位置及下标，应该从左到右进行更新，所以不用考虑回退问题。
参考基础的跳跃游戏，Ⅱ是基于一定可跳到最远处进行的最少次数求解问题。
一个下标对应的值为3，如果从当前下标起跳叫做第1次跳跃，那么从后面3个下标位置起跳都可以叫做第2次跳跃。
所以，当一次跳跃结束时，从下一个位置开始，到当前下标±3的位置（即最远的距离），都是下一次跳跃的范围（4~6）。
那我们可以遍历从4~6的位置尝试跳跃，直到试探到最远的位置，记录到max_index7。
跳完一次之后，更新下一次可以跳跃的范围（当前下标4~最远位置end6)。
直到跳到当前的范围边界end，此时更新范围边界，end=max_index。
在新的范围内跳，更新能跳到最远的距离max_index。
记录跳跃次数，如果跳到了终点，就得到了结果。
class Solution { public: int jump(vector<int>& nums) { int length = nums.size(); if(length == 1) return 0; int min_step = 0; int max_index = 0; int end = 0; for(int i = 0;i < length-1;i++) { max_index = max(nums[i] + i,max_index); if(i == end) { end = max_index; min_step++; } } return min_step; } };
