55：跳跃游戏

问题描述

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

示例

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

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

问题分析

这题乍一看挺难，其实仔细想想不难。
我们来剪断复杂的思维，比如我们想跳到最后一个格子，我们可以从前面任何一个格子起跳，只要有任何一个格子可以一次跳到最后一个格子，那么我们就把问题转化成了只要能达到它们，就可以跳到最后一个格子。逐渐的往前推。
这只是一种大体的思路，这种思路的复杂度至少也是O(n²)。我们还可以再优化一下。用记忆化技术来处理。其实这题用贪心就好，真的没必要用动态规划。

我们逆着刚刚的思路来想，如果对于某个格子来讲，前面的格子别管怎么组合都跳不到它，那么肯定是跳不到最后的。 而对于某个格子来讲，前面格子的组合能跳到它要怎么表示呢？？？我们可以记录一下前面的组合能够跳到的最大的距离，如果我们要求的格子在这个距离范围内，那么就能跳过去。(不要再想太多了，你管它从哪里跳的干什么，只要能跳过来就行)

所以我们根据这个策略可以写代码了。

AC代码

class Solution:
    def canJump(self, nums):
        remains = 0
        for i in range(nums):
            if remains < i:
                return False
            remains = max(remains,i+nums[i]) # i+nums[i]是在当前格子能跳到的最远的地方
        return True