题目：

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

解题思路：

1.要到达最后的位置，则如果前面没有值为0的点则必然可以到达

2.如果有值为0的点，则查看该点前的点的值是否可以跳过值为0的这个点到达下一个点，

3.如果有任意一个点可以满足，则该值0的点可以跳过，继续向后查找有没有值为0的点；

4.如果该值0的点无法跳过，则不能到达

5.所有点（最后一个点不需要判别）都不为0，或可以跳过，则可以到达。

代码：

  1. class Solution {
  2. public:
  3.     bool canJump(vector<int>& nums) {
  5.         for(int i = 0; i < nums.size() - 1; i++){
  6.             if(nums[i] != 0)
  7.                 continue;
  8.             bool flag = false;
  9.             for(int j = i - 1; j >= 0; j--){
  10.                 if(nums[j] > i - j){
  11.                     flag = true;
  12.                     continue;
  13.                 }
  14.             }
  15.             if(flag == false)
  16.                 return false;
  17.         }
  18.         return true;
  19.     }
  21. };
  22. //该方式为LeetCode代码风格，如果vs种运行，改成主函数格式的代码即可

总结：

可以直接用贪心等算法直接遍历，但是应用算法前可以先看看有没有可以简化的方式，对于这一题：

1.可以观察发现只要不含0就一定可以通过，从而简化。