LeetCode 45. 跳跃游戏 II（中等）

给定一个长度为 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]

问题分析

这道题是 55. 跳跃游戏 的进阶版。在第 55 题中，我们只需要判断是否能到达最后一个位置，而在这道题中，我们需要计算到达最后一个位置的最少跳跃次数。

关键点：

题目已经保证我们总能到达最后一个位置，所以不需要判断是否可达。
我们要找到的是最少的跳跃次数，这是一个优化问题。
由于数据规模为 10^4，我们需要设计时间复杂度不超过 O(n) 或 O(n log n) 的算法。

解题思路

贪心算法

这个问题可以使用贪心算法高效求解。关键思想是：在每次跳跃时，我们都选择下一步能到达的最远位置。

具体步骤：

初始化跳跃次数 jumps 为 0
初始化当前能到达的最远位置 currEnd 为 0
初始化下一步能到达的最远位置 currFarthest 为 0
遍历数组（除了最后一个元素，因为我们到达最后一个元素就结束了）：
1. 更新下一步能到达的最远位置：currFarthest = max(currFarthest, i + nums[i])
2. 如果当前位置已经到达了当前能到达的最远位置 currEnd：
  1. 增加跳跃次数：jumps++
  2. 更新当前能到达的最远位置为下一步能到达的最远位置：currEnd = currFarthest
返回跳跃次数 jumps

这种方法的关键在于，我们并不需要实际执行跳跃，而是通过预判下一步能到达的最远位置来确定在哪里进行下一次跳跃。

BFS（广度优先搜索）思想

这个贪心算法其实也可以看作是 BFS 的一种特殊形式。我们把每次跳跃能到达的所有位置看作是当前层，然后计算从这些位置出发能到达的下一层位置。这样，层数就代表了跳跃次数。

算法图解

以示例1为例：nums = [2,3,1,1,4]

让我们一步步跟踪算法的执行过程：

初始化：jumps = 0，currEnd = 0，currFarthest = 0
i = 0:
- nums[0] = 2，更新 currFarthest = max(0, 0+2) = 2
- 由于 i == currEnd，需要跳跃一次：jumps = 1，currEnd = 2
i = 1:
- nums[1] = 3，更新 currFarthest = max(2, 1+3) = 4
- i != currEnd，不需要跳跃
i = 2:
- nums[2] = 1，更新 currFarthest = max(4, 2+1) = 4
- 由于 i == currEnd，需要跳跃一次：jumps = 2，currEnd = 4
- 由于 currEnd >= nums.length - 1，已经可以到达终点，结束循环
返回 jumps = 2

详细代码实现

Java 实现 - 贪心算法

class Solution {public int jump(int[] nums) {// 如果数组长度为1，已经在终点，不需要跳跃if (nums.length == 1) {return 0;}int jumps = 0;        // 跳跃次数int currEnd = 0;      // 当前能到达的最远位置int currFarthest = 0; // 下一步能到达的最远位置// 遍历数组（除了最后一个元素）for (int i = 0; i < nums.length - 1; i++) {// 更新下一步能到达的最远位置currFarthest = Math.max(currFarthest, i + nums[i]);// 如果到达当前能到达的最远位置，需要进行一次跳跃if (i == currEnd) {jumps++;currEnd = currFarthest;// 如果已经可以到达最后一个位置，结束循环if (currEnd >= nums.length - 1) {break;}}}return jumps;}
}

C# 实现 - 贪心算法

public class Solution {public int Jump(int[] nums) {// 如果数组长度为1，已经在终点，不需要跳跃if (nums.Length == 1) {return 0;}int jumps = 0;        // 跳跃次数int currEnd = 0;      // 当前能到达的最远位置int currFarthest = 0; // 下一步能到达的最远位置// 遍历数组（除了最后一个元素）for (int i = 0; i < nums.Length - 1; i++) {// 更新下一步能到达的最远位置currFarthest = Math.Max(currFarthest, i + nums[i]);// 如果到达当前能到达的最远位置，需要进行一次跳跃if (i == currEnd) {jumps++;currEnd = currFarthest;// 如果已经可以到达最后一个位置，结束循环if (currEnd >= nums.Length - 1) {break;}}}return jumps;}
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组即可。

空间复杂度：O(1)，只使用了常数级的额外空间。

动态规划解法

虽然贪心算法已经是这个问题的最优解法，但我们也可以使用动态规划来解决它，以便理解问题的不同角度。

定义 dp[i] 为到达位置 i 的最少跳跃次数，那么状态转移方程为：

dp[i] = min(dp[j] + 1) 其中 j < i 且 j + nums[j] >= i

这意味着，对于位置 i，我们找到所有能到达 i 的位置 j，并选择跳跃次数最少的那个位置再加1。

Java 实现 - 动态规划

class Solution {public int jump(int[] nums) {int n = nums.length;int[] dp = new int[n];// 初始化dp数组，除了起点外，都初始化为最大值Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;// 计算到达每个位置的最少跳跃次数for (int i = 0; i < n; i++) {// 如果当前位置不可到达，跳过if (dp[i] == Integer.MAX_VALUE) {continue;}// 从当前位置可以跳到的所有位置for (int j = 1; j <= nums[i] && i + j < n; j++) {dp[i + j] = Math.min(dp[i + j], dp[i] + 1);}}return dp[n - 1];}
}

C# 实现 - 动态规划

public class Solution {public int Jump(int[] nums) {int n = nums.Length;int[] dp = new int[n];// 初始化dp数组，除了起点外，都初始化为最大值for (int i = 1; i < n; i++) {dp[i] = int.MaxValue;}dp[0] = 0;// 计算到达每个位置的最少跳跃次数for (int i = 0; i < n; i++) {// 如果当前位置不可到达，跳过if (dp[i] == int.MaxValue) {continue;}// 从当前位置可以跳到的所有位置for (int j = 1; j <= nums[i] && i + j < n; j++) {dp[i + j] = Math.Min(dp[i + j], dp[i] + 1);}}return dp[n - 1];}
}

这种动态规划解法的时间复杂度是 O(n²)，在最坏情况下（例如，nums 都是很大的数）会比贪心算法慢很多。但是对于理解问题的本质很有帮助。

贪心算法和动态规划的对比

贪心算法：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 优点：更快，使用更少的内存
- 思想：每一步都选择当前看起来最好的选择，而不考虑全局
动态规划：
- 时间复杂度：O(n²)
- 空间复杂度：O(n)
- 优点：更容易理解，适用范围更广
- 思想：将问题分解为子问题，并存储子问题的解以避免重复计算

在这个特定问题中，贪心算法是最佳选择，因为它既高效又正确。但在其他问题中，可能需要使用动态规划或其他算法。