跳跃游戏

题目描述：

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

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

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

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

思路:

从后往前遍历，能到的就为true

代码:

func canJump(nums []int) bool {
    isarrive := make([]bool, len(nums))
    isarrive[len(nums)-1] = true
    for i:= len(nums)-2 ;i>=0;i--{
        for j:=nums[i];j>0;j--{
            if j+i<len(nums) && isarrive[j+i] == true{
                isarrive[i] = true
                break
            }
        }
    }
    return isarrive[0] == true && isarrive[len(nums)-1]==true
}

代码效率：

执行用时：760 ms, 在所有 Go 提交中击败了5.05%的用户
内存消耗：2.2 MB, 在所有 Go 提交中击败了100.00%的用户

方法二，动态维护最大可到达区间

func canJump(nums []int) bool {
    maxJump := 0
    for i:=0;i<len(nums) && i<=maxJump;i++{
        maxJump = max(maxJump, nums[i]+i)
    }
    return maxJump>= len(nums)-1
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

执行用时：48 ms, 在所有 Go 提交中击败了87.34%的用户

内存消耗：6.7 MB, 在所有 Go 提交中击败了51.02%的用户