指尖划过的轨迹，藏着最细腻的答案~
题目
给定一个长度为 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:
输入: nums = [2,3,1,1,4]
输出: 2
解释:
跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000
- 题目保证可以到达 nums[n-1]
方法一：动态规划
根据题意，题目保障可以跳跃到最终位置n-1，最终需要寻找跳跃到最终位置n-1所需要的最小的跳跃次数，需要使用前面的信息，可以考虑使用 动态规划，而动态规划有三步，分别是：
-
明确dp数组含义： 本题我们定义dp[i]为到达下标i的最少跳跃次数，例如:
dp[2] = 2，即跳跃到下标2至少需要两次。 -
推导公式： 对于当前下标 i 来说，最大跳跃距离是
x = nums[i]，下标对应为j = i + x，即从i到j之间都可以一次跳跃到达；所以对于下标j来说，其最少的跳跃次数由两个方式决定，分别是i的跳跃次数dp[i] + 1与当前下标j的跳跃次数中的角小值，最终公式如下： $$ dp[j] = min(dp[j], dp[i] + 1) $$ -
初始化： 在i为0时，我们需要先将 i 为0时初始化，
dp[0] = nums[0];
AC代码：
class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();vector<int> dp(n, INT_MAX);dp[0] = 0;for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n && j <= i + nums[i]; j++) {dp[j] = min(dp[j], dp[i] + 1);}}return dp[n - 1];}
};
方法二：贪心
上面动态规划需要的时间复杂度为O($n^2$)，而使用贪心我们可以做到O(n)的时间复杂度。
这道题贪心的思路就是：在遍历nums数组时，尽可能的选择最远的i + nums[i]的值。
具体实现如下：
- 我们定义两个变量分别是遍历到当前i可以达到的最大的右端点
max_right与当前正在使用右端点cur_right； - 遍历
nums数组过程中，记录可以达到的最远的右端点：max_right = max(max_right, i + nums[i]) - 如果到达当前正在使用的右端点，说明
cur_ritht已不满足继续跳跃的条件，将cur_ritht更新为max_right，跳跃次数加一。
class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int ans = 0;int max_right = 0;int cur_ritht = 0;for (int i = 0; i < n - 1; i++) {max_right = max(max_right, i + nums[i]);if (i == cur_ritht) {cur_ritht = max_right;ans++;}}return ans;}
};