动态规划 跳跃游戏 II
LeetCode 45. 跳跃游戏 II
问题描述
给定一个非负整数数组 nums，初始位于数组的第一个位置。数组中的每个元素代表在该位置可以跳跃的最大长度。目标是使用最少的跳跃次数到达数组的最后一个位置（假设总是可以到达）。
示例：
示例 1:输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2:输入: nums = [2,3,0,1,4]输出: 2方法一：动态规划（反向查找）
算法思路
- 状态定义：
dp[i]表示从位置i到达数组末尾的最小跳跃次数。 - 初始化：末尾位置不需要跳跃（
dp[n-1] = 0）。 - 状态转移：对于每个位置
i，遍历它能跳到的所有位置j（i+1到i+nums[i]），取dp[j] + 1的最小值。 - 结果：返回
dp[0]（从起点到终点的最小跳跃次数）。
代码实现
class Solution { public int jump(int[] nums) { int n = nums.length; // dp[i] 表示从位置 i 到达末尾的最小跳跃次数 int[] dp = new int[n]; // 初始化：最后一个位置不需要跳跃 dp[n - 1] = 0; // 从后向前计算每个位置的最小跳跃次数 for (int i = n - 2; i >= 0; i--) { // 如果当前位置可以直接跳到末尾 if (i + nums[i] >= n - 1) { dp[i] = 1; } else { // 初始化为一个较大值（表示暂时不可达） dp[i] = Integer.MAX_VALUE - 1; // 防止后续 +1 溢出 // 遍历当前位置能跳到的所有位置 for (int j = i + 1; j <= i + nums[i] && j < n; j++) { // 如果位置 j 可达，则更新 dp[i] if (dp[j] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } } return dp[0]; }}复杂度分析
- 时间复杂度：O(n²)，其中 n 是数组长度。每个位置可能需要遍历最多 n 个位置。
- 空间复杂度：O(n)，用于存储 dp 数组。
方法二：贪心算法（正向查找）
算法思路
- 核心变量：
steps：记录当前跳跃次数。end：当前步数能到达的最远边界。maxPos：下一步能到达的最远位置。
- 遍历数组：
- 更新
maxPos = max(maxPos, i + nums[i])。 - 当遍历到当前边界
end时：- 跳跃次数
steps++。 - 更新边界
end = maxPos（表示进入下一步）。
- 跳跃次数
- 提前终止：如果
end已覆盖终点，直接结束。
- 更新
- 结果：返回跳跃次数
steps。
代码实现
class Solution { public int jump(int[] nums) { int n = nums.length; int steps = 0; // 跳跃次数 int end = 0; // 当前步数能到达的边界 int maxPos = 0; // 下一步能到达的最远位置 // 遍历数组（注意终点不需要再跳） for (int i = 0; i < n - 1; i++) { // 更新下一步能跳到的最远位置 maxPos = Math.max(maxPos, i + nums[i]); // 到达当前步数的边界，必须进行下一次跳跃 if (i == end) { steps++; // 增加跳跃次数 end = maxPos; // 更新边界 // 如果新边界已覆盖终点，提前结束 if (end >= n - 1) break; } } return steps; }}复杂度分析
- 时间复杂度：O(n)，只需遍历数组一次。
- 空间复杂度：O(1)，仅使用常数空间。
算法过程（贪心法）
nums = [2,3,1,1,4] ：
- 初始化：
steps=0, end=0, maxPos=0。 - 遍历：
i=0：maxPos = max(0, 0+2)=2→ 到达边界end=0→steps=1,end=2。i=1：maxPos = max(2, 1+3)=4（边界未更新）。i=2：maxPos = max(4, 2+1)=4→ 到达边界end=2→steps=2,end=4。i=3：maxPos不变 → 边界end=4已覆盖终点，循环结束。
- 结果：
steps=2。
测试用例
public static void main(String[] args) { Solution solution = new Solution(); // 测试用例1: 标准示例 int[] nums1 = {2,3,1,1,4}; System.out.println(\"Test 1: \" + solution.jump(nums1)); // 2 // 测试用例2: 起点即终点 int[] nums2 = {0}; System.out.println(\"Test 2: \" + solution.jump(nums2)); // 0 // 测试用例3: 需要连续跳跃 int[] nums3 = {1,2,1,1,1}; System.out.println(\"Test 3: \" + solution.jump(nums3)); // 3 // 测试用例4: 大跨度跳跃 int[] nums4 = {2,3,0,1,4}; System.out.println(\"Test 4: \" + solution.jump(nums4)); // 2 // 测试用例5: 递增序列 int[] nums5 = {1,2,3,4,5}; System.out.println(\"Test 5: \" + solution.jump(nums5)); // 3}关键点
- 动态规划：
- 反向计算最小跳跃次数。
- 适用于理解状态转移，但效率较低（O(n²)）。
- 贪心算法：
核心思想：每一步都跳到未来潜力最大的位置。- 边界更新：当遍历到当前边界时，意味着必须进行下一次跳跃。
- 提前终止：若边界已覆盖终点，直接结束。
- 最优选择：时间复杂度 O(n)，空间复杂度 O(1)，是本题最优解法。
常见问题
- 为什么贪心算法中循环条件是
i < n-1？
终点不需要跳跃，且当end覆盖终点时可提前终止。 - 贪心算法的正确性保证？
每一步都扩展了下一步的最大覆盖范围，确保跳跃次数最小。 - 动态规划为何效率低？
每个位置需遍历其后所有可达位置，最坏情况时间复杂度 O(n²)。
为什么动态规划使用反向查找？
1. 问题依赖关系的方向性
- 跳跃方向：从位置
i只能向后跳跃（i → i+1, i+2, ..., i+nums[i]）。 - 状态依赖：要计算
dp[i]（从i到终点的最小步数），必须知道i后方位置的状态（dp[i+1],dp[i+2], …）。 - 反向计算：从终点开始倒序计算，确保计算
dp[i]时，其依赖的所有dp[j]（j > i）都已计算完成。
2. 正向查找的缺陷
若尝试正向计算（从起点向终点）：
public int jump(int[] nums) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (j + nums[j] >= i) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n-1];}- 问题 1：计算
dp[i]时，dp[j]可能未达到最优解（动态规划要求无后效性）。 - 问题 2：需要遍历所有
j < i，最坏时间复杂度 O(n²)，且无法利用跳跃特性优化。
3. 反向查找的优势
(1) 自然符合状态依赖
for (int i = n - 2; i >= 0; i--) { for (int j = i + 1; j <= i + nums[i]; j++) { dp[i] = Math.min(dp[i], dp[j] + 1); // 依赖后方状态 }}- 倒序计算确保
dp[j]在dp[i]之前已求解。
(2) 提前终止优化
if (i + nums[i] >= n - 1) { dp[i] = 1; // 直接跳到终点}- 若从
i可直接跳到终点，无需遍历后续位置。
(3) 逻辑清晰
- 状态定义：
dp[i] = \"从 i 到终点的最小步数\"符合直觉。 - 目标明确：直接返回
dp[0]（起点到终点的解）。
无后效性要求
动态规划的核心要求之一是无后效性：一个子问题的解一旦确定，就不应受后续状态的影响：
- 状态定义应该包含确定问题解的所有必要信息
- 状态转移不应依赖未求解的状态
- 状态一旦计算完成，其值不应再改变
