关于跳跃问题 #1
Description
问题描述：给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
解题思路：
这个题，第一时间想到的是递归回溯，就是从数组的第一个位置开始，针对这个位置上的值，从0开始往后推导，如果中间推导到一个不可能到达最后位置的位置，那么就回溯，继续别的推导。思路很简单，唯一的缺点是，贼鸡儿慢！时间复杂度是2的n次方，详细推导见leetcode。
然后又开始想别的方法，比如添加一个记忆表来优化，并从后往前遍历。先给每个位置赋予一个boolean变量，初始所有都是false（除了最后一个是good）。从最后一个开始往前遍历，如果这个位置可以到达一个good位置，那么把这个位置设为good。如果0的位置是good，那么说明可以到达最后一个位置。
然而这个方法也是可以优化的，我们想想，我遍历过程中，每次判断实际上只是判断了从0到num[i]中，最左边的那个good是否能到达，没有考虑所有的后面的good，所以我直接用一个指针来指向最左边的good，这样不仅不用boolean数组，而且遍历判断的时候不用递增地去一个个比较，而是直接和这个指针比较就ok。