【LeetCode 热题100】45：跳跃游戏 II（详细解析）（Go语言版）

🚀 力扣 45：跳跃游戏 II（全解法详解）

📌 题目描述

给你一个非负整数数组 nums，表示你最初位于数组的第一个位置。

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

你的目标是使用 最少的跳跃次数 到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

🎯 示例 1：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到位置 1（跳 1 步），然后跳 4（再跳 1 步）——共 2 步

🎯 示例 2：

输入: nums = [2,3,0,1,4]
输出: 2

---

💡 解题思路总览

我们要找到 从起点跳到终点的最少步数。这题与「跳跃游戏 I」不同的地方是，这次我们不是判断“能否到达”，而是要求最小的“跳跃次数”。

---

✅ 解法一：贪心算法（最推荐🔥）

✨ 核心思路：

使用贪心思想，在每一步跳跃时，选择能跳的最远的那个位置。

🧠 实现步骤：

1. 初始化步数 steps = 0，当前跳跃的边界 end = 0，和当前最远位置 farthest = 0
2. 遍历数组：
   • 每次更新当前最远能跳到的位置
   • 当到达当前边界时，步数加一，并更新边界为 farthest

💻 代码实现（Go）：

func jump(nums []int) int {steps := 0end := 0farthest := 0for i := 0; i < len(nums)-1; i++ {farthest = max(farthest, i+nums[i])if i == end {steps++end = farthest}}return steps
}func max(a, b int) int {if a > b {return a}return b
}

⏱️ 时间复杂度：O(n)

🧠 空间复杂度：O(1)

---

🔄 解法二：动态规划（自底向上）

✨ 核心思路：

定义 dp[i] 表示从位置 i 跳到终点所需的最小步数。

🧠 实现步骤：

1. 初始化 dp[n-1] = 0（终点到终点步数为0）
2. 从右向左遍历数组
3. 对于每个 i，从 i+1 到 i+nums[i] 找 dp[j] 中最小值

💻 代码实现（Go）：

func jump(nums []int) int {n := len(nums)dp := make([]int, n)for i := n - 2; i >= 0; i-- {minStep := int(1e9)for j := i + 1; j <= i+nums[i] && j < n; j++ {if dp[j] < minStep {minStep = dp[j]}}dp[i] = minStep + 1}return dp[0]
}

⏱️ 时间复杂度：O(n²)

🧠 空间复杂度：O(n)

💬 优点：清晰易懂，适合入门
❗ 缺点：效率较低，不适合数据量大的情况

---

🔁 解法三：反向贪心（从终点往回跳）

✨ 核心思路：

从终点出发，每次选择最靠前、但能够跳到当前终点的位置，更新目标点，直到回到起点。

🧠 实现步骤：

1. 初始位置设为 pos = n-1
2. 遍历数组从头找哪个位置能跳到 pos
3. 每次成功找到，就将 pos 更新为当前索引，同时步数加一

💻 代码实现（Go）：

func jump(nums []int) int {pos := len(nums) - 1steps := 0for pos > 0 {for i := 0; i < pos; i++ {if i+nums[i] >= pos {pos = isteps++break}}}return steps
}

⏱️ 时间复杂度：O(n²)

🧠 空间复杂度：O(1)

💬 优点：逻辑反向，易于验证正确性
❗ 缺点：效率低，不适合大数据量

---

📊 三种方法对比总结

解法	时间复杂度	空间复杂度	适合场景	特点说明
✅ 贪心	O(n)	O(1)	面试首选	高效实用，核心技巧
动态规划	O(n²)	O(n)	教学/入门	思路清晰，但慢
反向贪心	O(n²)	O(1)	验证/反向思考	逆向推理，有趣但低效

---

📌 最佳实践建议

• 面试中建议优先写贪心算法，能体现算法思维和代码能力；
• 若初学 DP，可尝试动态规划方式，加深状态转移理解；
• 想换个角度思考，可尝试反向贪心，拓展思维维度。

---

📚 拓展阅读

• Leetcode 55. 跳跃游戏 I
• Leetcode 134. 加油站（贪心）
• Leetcode 122. 买卖股票的最佳时机 II（贪心）

---

💡 如果你觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 📌，我将持续更新更多 LeetCode 热题的高质量解析～

---