贪心算法：跳跃游戏

思路：第一反应是回溯问题，不断穷举nums【i】可能经过的路线，但是很遗憾，运行超时了

代码如下，也算是提供思路吧：

class Solution {public:bool canJump(vector<int>& nums) {if(nums.size() == 1)return true;int startIndex = 0;bool flag = false;backtrack(nums, startIndex, flag);return flag;}void backtrack(vector<int>& nums, int startIndex, bool& flag){//退出if(startIndex >= nums.size() - 1){flag = true;return;}for(int i = 1; i <= nums[startIndex]; i++){backtrack(nums, startIndex + i, flag);if(flag == true)break;}}};

另一种思路：我们发现阻挡我们前进的只有元素0，因此只要判断我们能否跨过值为0的元素，那么我们就能继续前进：

class Solution {public:bool canJump(vector<int>& nums) {if(nums.size() == 1)return true;bool flag = 1;for (int i = 0; i < nums.size(); i++){//第一位是0if (i == 0 && nums[i] == 0){return false;}else if (i > 0 && i < nums.size() - 1){if (nums[i] == 0)//检验之前的数字是否能跳过0{int startIndex = i - 1;while (startIndex >= 0){int step = nums[startIndex] - (i - startIndex);if (step <= 0){flag = false;}else{//能跳过0，那么继续往后判断即可flag = true;break;}startIndex--;}//遇到0不能跳过，之间返回falseif(flag == false)return flag;}}}return flag;}};

那我们换种思路，用贪心算法来看看这道题：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

每次i只能在cover区间内取值

class Solution {public:bool canJump(vector<int>& nums) {if(nums.size() == 1)return true;int cover = 0;for(int i = 0; i <= cover; i++){cover = max(cover, i + nums[i]);if(cover >= nums.size() - 1)return true;}return false;}};