前言

今天也是两道题，两道都是中等，其中一道是变体

题目1

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

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

示例 1：

示例 2：

提示：

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

分析

这道题暴力解法很简单，双层for循环，时间复杂度为O(n ^ 2)，根据官方的尿性，这个方案我们可以直接跳过。

前面我们说过，这个数组只是一维的，那么大部分情况下我们都可以在O(n)的情况下实现。

我们怎么知道这条路可以走到头呢？只要最后一步可以跳出即可。如果这个元素的值是0，那这条路就是断了。

前面我们还说过，看到最长、最短、最大、最小我们可以思考下是否可以用动态规划实现。

那么我们这道题能不能呢？当然可以。

那么走流程：

1. 确认目标，根据求什么设什么，dp[i]表示当前最大可以跳的距离；
2. 找关系：很明显当前这一步和之前一步有关系，之前一步可能可以跳的比当前这一步的远，所以选择最远那个，所以存在dp[i] = max(dp[i - 1], nums[i] + i)的关系。
3. 初始值：因为我们需要dp[i - 1]，所以初始需要处理第一个
4. 优化：我们只需要上一个元素，所以我们并不需要记录整个数组，所以我们搞个变量记录下即可。

解

代码没啥好说的

测试用例

题目2

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

示例 2:

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

分析

结合上一题的解法，我们这题基本上没多大变化，因为每次都是最远跳跃距离意味着整体最少跳跃次数。

但是，这道题需要我们绕个弯（还是那句话：数理思维）。

这道题有个重点，跳跃的距离和当前正在跳是冲突的，简单地说就是步伐和正在走的这一步的关系，你的脚已经在半空中了，你可以调整步伐，但是只能在脑子里调整，当前这一步要怎么走已经是确定好的了。

放到这道题中就是，你这一个元素要跳的这段距离我们都得走一遍（正在走的那一步），然后取里面绝对路径可以跳的最远那货即可（也就是调整步伐，自然是选最远的）。

解

测试用例

总结

第一道题我们可以想出来，不过第二道题就比较灵活了，需要绕弯，尤其是当我们做完第一题之后直接做第二道题，很容易就进入坑里，思维还停留在第一道题里。

还是得多做啊