55.跳跃游戏

题面：

给你一个非负整数数组 nums，你最初位于数组的 第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

 

示例 1：

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

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

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

朴素的状态转移方程：如果某个坐标能到达，且能跳到 i, 那么 i 也能到达

复杂度是：O(N^2);太大了，但是 leetcode 也能过;

dp[0] = true
n := len(nums)
for i:=1;i<n;i++{ // 0 已经被列出来了;
    for j:=0;j<i;j++{ // 0 ~ i-1
        if dp[j] && dp[j]+nums[j] >= i {
            dp[i] = true
        }
    }
}
return dp[n-1]

还能优化下：

背包 dp 的写法，当 dp[i]为 true 时，往后的 step 步都是 true, 注意不要越界;

以下是个 O(n) 的写法：

dp[0] = true
n := len(nums)
for i:=0;i<n;i++{ // 因为逻辑是从已经算出来的推断后面的，所以从 0 开始
    if(dp[i]){ 
        for step:=1;step <= nums[i] && i + step < n;step++ { //step 不能越界; 1，不能超过 n; 2, 不能超过步数
            dp[i+step] = true
        }
    }
}

还能通过状态压缩，压缩到 O(1): 就是把全是 T 的路径给统一起来：

dp[0] = true
n := len(nums)
maxPos := 0
for i:=0;i<n;i++{ // 因为逻辑是从已经算出来的推断后面的，所以从 0 开始
    if i > maxPos {
        return false
    }
    maxPos = max(i+maxPos,maxPos)
}

TIP

待补充

TIP

需要抓住问题的本质对应的模型，并且总结该模型对应的解题思路; 这样在遇到相同的模型时，才能更快的看破;

55.跳跃游戏 ​

题面： ​

55.跳跃游戏

题面：