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

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

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

示例 1:

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

示例 2:

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

 

这个题记忆化搜索都会炸，呵呵。

class Solution:    def __init__(self):        self.ans = False        self.vis = [ False for _ in range(1000000)]        self.vis[0] = True    def canJump(self, nums):        """        :type nums: List[int]        :rtype: bool        """        def dfs(pos):            if pos == len(nums) - 1 :                self.ans = True            for i in range(nums[pos],0,-1):                if self.ans == True:                    break                if pos+i < len(nums):                    if not self.vis[pos+i]:                        self.vis[pos+i] = True                        dfs(pos+i)                        self.vis[pos+i] = False        dfs(0)        return self.ans

 

贪心大法：

维护能够到达的最远位置，注意前面的都要能够到达，否则这个想法就不对了。对于第一个位置，就是前面的都能到达。

class Solution:    def canJump(self, nums):        """        :type nums: List[int]        :rtype: bool        """        max_pos = 0        for i in range(len(nums)):            if i > max_pos:                return False            max_pos = max(max_pos, i+nums[i])        return max_pos >= len(nums)-1