问题描述
给定一个非负数数组 arr[]，每个元素表示从该位置最多可向前跳跃的步数。
示例：
- 若 arr[i] = 3，则可以从位置 i 跳跃到 i+1、i+2 或 i+3。
- 若 arr[i] = 0，则无法从该位置向前跳跃。
任务：找到从数组第一个位置移动到最后一个位置所需的最小跳跃次数。
注意：若无法到达终点，返回 -1。
示例
输入: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
输出: 3
解释:
第一次从第 1 个元素（值 1）跳到第 2 个元素（值 3）。
第二次从第 2 个元素跳到第 5 个元素（值 9）。
第三次从第 5 个元素跳到终点。
输入: arr = [1, 4, 3, 2, 6, 7]
输出: 2
解释:
第一次从第 1 个元素跳到第 2 个元素，第二次跳到终点。
输入: arr = [0, 10, 20]
输出: -1
解释: 无法从第一个位置跳跃。
方法 1：递归（时间复杂度 O(nⁿ)，空间复杂度 O(n)）
核心思想：递归遍历所有可能的跳跃路径，返回最小跳跃次数。
public class JumpGame {// 递归函数：计算从位置i到终点的最小跳跃次数 private static int minJumpsRecursive(int[] arr, int i) {// 终止条件：当前已到达或超过终点 if (i >= arr.length - 1) return 0;int minSteps = Integer.MAX_VALUE;// 遍历所有可能的跳跃步数（1到arr[i]步） for (int j = 1; j <= arr[i]; j++) {int nextPos = i + j;// 递归计算从下一步到终点的最小跳跃次数 int steps = minJumpsRecursive(arr, nextPos);if (steps != Integer.MAX_VALUE) {minSteps = Math.min(minSteps, 1 + steps); // 当前跳跃+后续步数 }}return minSteps;}public static int minJumps(int[] arr) {int result = minJumpsRecursive(arr, 0);return result == Integer.MAX_VALUE ? -1 : result;}public static void main(String[] args) {int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};System.out.println(minJumps(arr)); // 输出：3}
}-
-
-
方法 2：动态规划（时间复杂度 O(n²)，空间复杂度 O(n)）
-
-
核心思想：自底向上填充 dp[i]，表示从 i 到终点的最小跳跃次数。
public class JumpGameDP {public static int minJumps(int[] arr) {int n = arr.length;int[] dp = new int[n];Arrays.fill(dp, Integer.MAX_VALUE);dp[n - 1] = 0; // 终点到终点的跳跃次数为0 // 从倒数第二个元素向前推导 for (int i = n - 2; i >= 0; i--) {// 最多可跳跃到的最远位置 int maxJump = Math.min(i + arr[i], n - 1);for (int j = i + 1; j <= maxJump; j++) {if (dp[j] != Integer.MAX_VALUE) {dp[i] = Math.min(dp[i], 1 + dp[j]); // 选择最小的跳跃次数 }}}return dp[0] == Integer.MAX_VALUE ? -1 : dp[0];}public static void main(String[] args) {int[] arr = {1, 3, 5, 1, 3, 2, 6, 7, 6, 8, 9}; System.out.println(minJumps(arr)); // 输出：4int[] arr1 = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};System.out.println(minJumps(arr1)); // 输出：3}
}
说明：
- 初始化：dp[n-1] = 0（终点无需跳跃）。
- 填表顺序：从后向前，每个位置依赖后续位置的结果。
- 优势：无需递归栈，空间更优。
方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 核心优化 |
| 暴力递归 | O(nⁿ) | O(n) | 无 |
| 动态规划（自底向上） | O(n²) | O(n) | 迭代填表，无需递归栈 |