13-跳跃游戏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]。

方法一： 贪心算法

这是一个典型的贪心算法问题，要求计算到达数组最后一个位置的最小跳跃次数。以下是使用 TypeScript 实现的代码：

代码实现 function jump(nums: number[]): number { const n = nums.length; if (n === 1) { return 0; } // 当前跳跃能到达的最远位置 let currentMaxReach = 0; // 下一步跳跃能到达的最远位置 let nextMaxReach = 0; // 跳跃次数 let jumps = 0; for (let i = 0; i < n - 1; i++) { // 更新下一步跳跃能到达的最远位置 nextMaxReach = Math.max(nextMaxReach, i + nums[i]); // 如果当前位置到达了当前跳跃能到达的最远位置 if (i === currentMaxReach) { // 进行一次跳跃 jumps++; // 更新当前跳跃能到达的最远位置为下一步跳跃能到达的最远位置 currentMaxReach = nextMaxReach; // 如果当前跳跃能到达的最远位置已经可以到达数组的最后一个位置，直接返回跳跃次数 if (currentMaxReach >= n - 1) { break; } } } return jumps; } // 示例调用 const nums = [2, 3, 1, 1, 4]; const minJumps = jump(nums); console.log("到达数组最后一个位置的最小跳跃次数:", minJumps); 代码解释 边界条件处理：如果数组长度为 1，说明已经在最后一个位置，不需要跳跃，直接返回 0。初始化变量： currentMaxReach：表示当前跳跃能到达的最远位置，初始化为 0。nextMaxReach：表示下一步跳跃能到达的最远位置，初始化为 0。jumps：表示跳跃次数，初始化为 0。 遍历数组： 在遍历过程中，不断更新 nextMaxReach，它是当前位置 i 加上该位置能跳跃的最大长度 nums[i] 与之前的 nextMaxReach 中的较大值。当 i 等于 currentMaxReach 时，说明已经到达了当前跳跃能到达的最远位置，此时需要进行一次跳跃，jumps 加 1。同时更新 currentMaxReach 为 nextMaxReach，表示进入下一次跳跃的范围。如果 currentMaxReach 已经大于等于数组的最后一个位置的索引 n - 1，说明已经可以到达最后一个位置，直接跳出循环。 返回结果：遍历结束后，jumps 即为到达数组最后一个位置的最小跳跃次数，将其返回。 复杂度分析 时间复杂度：O(n)，其中  是数组的长度。因为只需要对数组进行一次遍历。空间复杂度：O(1)，只使用了常数级的额外变量。

这种贪心算法的核心思想是在每一次跳跃中，尽可能地跳到最远的位置，从而用最少的跳跃次数到达数组的最后一个位置。

方法二： 广度优先搜索

除了前面介绍的贪心算法，还可以使用广度优先搜索（BFS）的方法来解决这个问题。BFS 的核心思想是从起始位置开始，逐层扩展所有可能的跳跃位置，直到到达目标位置，每扩展一层就相当于进行了一次跳跃，记录扩展的层数即为最小跳跃次数。

代码实现 function jump(nums: number[]): number { const n = nums.length; if (n === 1) { return 0; } // 记录已经访问过的位置 const visited = new Array(n).fill(false); // 初始化队列，队列中存储 [当前位置, 跳跃次数] const queue: [number, number][] = [[0, 0]]; visited[0] = true; while (queue.length > 0) { const [currentIndex, jumps] = queue.shift()!; // 遍历当前位置能跳跃到的所有位置 for (let j = 1; j <= nums[currentIndex] && currentIndex + j < n; j++) { const nextIndex = currentIndex + j; // 如果到达了最后一个位置，返回当前跳跃次数加 1 if (nextIndex === n - 1) { return jumps + 1; } // 如果该位置未被访问过 if (!visited[nextIndex]) { // 标记为已访问 visited[nextIndex] = true; // 将该位置和跳跃次数加 1 加入队列 queue.push([nextIndex, jumps + 1]); } } } return -1; // 理论上不会执行到这里，因为题目保证可以到达最后一个位置 } // 示例调用 const nums = [2, 3, 1, 1, 4]; const minJumps = jump(nums); console.log("到达数组最后一个位置的最小跳跃次数:", minJumps); 代码解释 边界条件处理：如果数组长度为 1，说明已经在最后一个位置，不需要跳跃，直接返回 0。初始化变量： visited：一个布尔类型的数组，用于记录每个位置是否已经被访问过，初始时所有位置都标记为未访问。queue：一个队列，用于存储待扩展的位置和对应的跳跃次数，初始时将起始位置 0 和跳跃次数 0 加入队列，并将起始位置标记为已访问。 BFS 过程： 当队列不为空时，从队列中取出一个元素，包含当前位置 currentIndex 和跳跃次数 jumps。遍历当前位置能跳跃到的所有位置 nextIndex（范围是从 currentIndex + 1 到 currentIndex + nums[currentIndex] 且不超过数组长度）。如果 nextIndex 是最后一个位置，说明已经到达目标，返回当前跳跃次数加 1。如果 nextIndex 未被访问过，将其标记为已访问，并将 [nextIndex, jumps + 1] 加入队列。 返回结果：如果一切正常，在 BFS 过程中会找到到达最后一个位置的最小跳跃次数并返回；理论上不会执行到返回 -1 的情况，因为题目保证可以到达最后一个位置。 复杂度分析 时间复杂度：O(n)，其中  是数组的长度。每个位置最多被访问一次，因此时间复杂度为线性。空间复杂度：O(n)，主要用于存储 visited 数组和队列，队列在最坏情况下可能存储所有位置。

与贪心算法相比，BFS 方法的代码实现相对复杂一些，但它的思路更加直观，适合用于解决一些需要搜索所有可能路径的问题。不过，在这个特定问题中，贪心算法的时间和空间复杂度虽然与 BFS 相同，但在实际运行中可能会更快，因为贪心算法不需要维护队列和访问标记数组。

方法三： 动态规划

动态规划的核心思想是将原问题分解为子问题，通过求解子问题的最优解来得到原问题的最优解。

思路分析 定义状态：设 dp[i] 表示到达数组中第 i 个位置所需的最小跳跃次数。初始化状态：dp[0] = 0，因为初始位置就在 nums[0]，不需要跳跃。对于其他位置 i，初始化为一个较大的值（比如 Infinity），表示暂时无法到达。状态转移方程：对于每个位置 i，遍历其前面的所有位置 j（0 <= j < i），如果从位置 j 能够跳到位置 i（即 j + nums[j] >= i），则更新 dp[i] 为 dp[j] + 1 和 dp[i] 中的较小值。最终结果：dp[n - 1] 即为到达数组最后一个位置所需的最小跳跃次数。 代码实现 function jump(nums: number[]): number { const n = nums.length; // 初始化 dp 数组，dp[i] 表示到达第 i 个位置所需的最小跳跃次数 const dp: number[] = new Array(n).fill(Infinity); // 初始位置不需要跳跃 dp[0] = 0; // 遍历数组中的每个位置 for (let i = 1; i < n; i++) { // 遍历 i 之前的所有位置 for (let j = 0; j < i; j++) { // 如果从位置 j 能够跳到位置 i if (j + nums[j] >= i) { // 更新 dp[i] 为 dp[j] + 1 和 dp[i] 中的较小值 dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n - 1]; } // 示例调用 const nums = [2, 3, 1, 1, 4]; const minJumps = jump(nums); console.log("到达数组最后一个位置的最小跳跃次数:", minJumps); 复杂度分析 时间复杂度：O(n^2)，其中  是数组的长度。因为需要使用两层嵌套循环来填充 dp 数组。空间复杂度：O(n)，主要用于存储 dp 数组。 代码解释 初始化 dp 数组：创建一个长度为 n 的数组 dp，并将所有元素初始化为 Infinity，表示暂时无法到达。将 dp[0] 设为 0，因为初始位置不需要跳跃。填充 dp 数组：使用两层嵌套循环，外层循环遍历从 1 到 n - 1 的每个位置 i，内层循环遍历从 0 到 i - 1 的每个位置 j。对于每个位置 j，如果从位置 j 能够跳到位置 i（即 j + nums[j] >= i），则更新 dp[i] 为 dp[j] + 1 和 dp[i] 中的较小值。返回结果：最终返回 dp[n - 1]，即到达数组最后一个位置所需的最小跳跃次数。

动态规划方法虽然可以解决这个问题，但时间复杂度较高，在处理大规模数组时性能可能不如贪心算法。贪心算法的时间复杂度为 ，是更优的解决方案。