跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个 下标 。数组中的每个元素代表你在该位置可以跳跃的 最大长度 。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路一：贪心算法

function canJump(nums) {let maxReach = 0; // 当前能到达的最远距离let currPos = 0; // 当前位置的索引for (let i = 0; i < nums.length; i++) {// 如果当前位置已经无法通过之前的跳跃到达，直接返回falseif (i > maxReach) return false;// 更新能到达的最远距离maxReach = Math.max(maxReach, i + nums[i]);// 如果最远距离已经可以到达最后一个位置，提前返回trueif (maxReach >= nums.length - 1) return true;// 移动到下一个位置currPos = i + 1;}// 如果遍历结束还没有返回，说明无法到达最后一个位置，返回falsereturn false;
}

讲解
解决这个问题，可以采用贪心算法的思路，动态规划也可以，但贪心算法更简洁高效。核心思想是维护一个可达到的最远距离，每次更新这个最远距离，并用它来决定>下一步的跳跃位置。

1. 初始化：设置两个变量，maxReach 用来记录当前位置能够跳跃到的最远距离，currPos 用来记录当前所在位置的索引（初始为 0 ）。
2. 遍历：从数组的开始位置遍历，对于每个位置 i ，检查 i + nums[i] 是否大于 maxReach ，如果是，则更新 maxReach 为这个更大的值。这表示我们可以在当前位置通过一次跳跃到达更远的地方。
3. 判断结束条件：如果在某次遍历中，currPos 加上当前步长能覆盖数组的最后一个位置，或者 maxReach 已经超过了数组的最后一个位置，说明可以到达数组的最后一个位置，返回 true 。反之，如果在遍历完数组之前，无法再进行有效跳跃（即 currPos 达到了 maxReach 但还没到达数组末尾），则返回 false 。

思路二：动态规划

var canJump = function (nums) {const dp = new Array(nums.length).fill(false);dp[0] = true; // 从第一个下标开始是可以到达的for (let i = 0; i < nums.length; i++) {if (dp[i]) {for (let j = 1; j <= nums[i] && i + j < nums.length; j++) {dp[i + j] = true; // 标记可以到达的下标}}}return dp[nums.length - 1]; // 返回最后一个下标是否可达
};

讲解

1. DP 数组定义
   我们定义一个布尔数组 dp，其中 dp[i] 表示从起始位置（第一个下标）到达下标 i 是否是可行的。初始时，dp[0] 为 true，因为我们一开始就在第一个下标。
2. 状态转移
   • 初始化：dp[0] = true，表示起始位置是可达的。
   • 遍历数组：对于每一个下标 i：
     1. 如果 dp[i] 为 true，表示可以从起始位置跳跃到 i ，那么我们可以尝试跳跃到 i 后面的下标。
     2. 根据 nums[i] 的值，计算可以跳跃到的范围：i + 1 到 i + nums[i]。
     3. 在这个范围内的每一个下标 j（确保 j 不超出数组边界），我们将 dp[j] 设置为 true，表示可以从起始位置跳跃到下标 j。
   • 终止条件：如果在遍历过程中，发现 dp[nums.length - 1] 为 true，则说明可以到达最后一个下标，返回 true。如果遍历结束后仍然为 false，返回 false。

思路三：递归 + 记忆化搜索

function canJump(nums) {const memo = new Array(nums.length).fill(-1); // -1 表示未计算return canJumpFromPosition(0, nums, memo);
}function canJumpFromPosition(position, nums, memo) {if (position >= nums.length - 1) return true; // 已经到达或超过最后一个下标if (memo[position] !== -1) return memo[position] === 1; // 如果已经计算过，直接返回结果const furthestJump = Math.min(position + nums[position], nums.length - 1);for (let i = position + 1; i <= furthestJump; i++) {if (canJumpFromPosition(i, nums, memo)) {memo[position] = 1; // 标记为可达return true;}}memo[position] = 0; // 标记为不可达return false;
}

讲解
通过递归，我们可以尝试从当前下标跳跃到所有可能的下标，并记录已经计算过的结果，以避免重复计算。

1. 基础条件：
   • 如果当前下标 position 已经到达或超过最后一个下标，返回 true。
   • 如果当前下标已经被访问过且结果为 false，则返回 false。
2. 递归逻辑：
   • 从当前位置 position，计算可以跳跃到的最远位置 furthestJump，即 position + nums[position]，但不能超过数组边界。
   • 对于从 position + 1 到 furthestJump 的每个下标，递归调用函数来检查是否可以到达最后一个下标。如果能达到，返回 true。
   • 如果所有可能的跳跃都无法到达最后一个下标，则将当前位置标记为不可达，并返回 false。
3. 记忆化搜索：
   • 使用一个数组 memo 来存储每个下标的计算结果，避免重复计算。数组的初始值为 -1，表示尚未计算。
   • 如果当前位置已经计算过，直接返回存储的结果。

思路四：广度优先搜索 (BFS)

var canJump = function (nums) {const queue = [0]; // 从第一个下标开始const visited = new Set(); // 用于记录访问过的下标while (queue.length > 0) {const current = queue.shift();if (current >= nums.length - 1) return true; // 如果已经到达最后一个下标for (let i = 1; i <= nums[current]; i++) {const next = current + i;if (next < nums.length && !visited.has(next)) {visited.add(next); // 标记为已访问queue.push(next); // 加入队列}}}return false; // 如果队列为空，返回 false
};

讲解
通过 BFS，我们可以逐层探索每个可跳跃的位置，直到找到是否能够到达最后一个下标。

1. 初始化：
   • 使用一个队列来存储当前可以访问的位置。
   • 将起始位置（下标 0）加入队列。
   • 使用一个布尔数组 visited 来标记已经访问过的位置，以避免重复访问。
2. 遍历过程：
   • 从队列中取出当前下标 current，检查是否已经到达最后一个下标。如果是，返回 true。
   • 计算从 current 可以跳跃到的最远位置 furthestJump，即 current + nums[current]。
   • 遍历从 current + 1 到 furthestJump 的所有下标，检查是否已经访问过。如果没有，则将这些下标加入队列，并标记为已访问。
3. 终止条件：
   • 如果队列为空且仍未到达最后一个下标，则返回 false。

思路五：深度优先搜索 (DFS)

function canJump(nums) {const visited = new Set();return dfs(0, nums, visited);
}function dfs(position, nums, visited) {if (position >= nums.length - 1) return true; // 已经到达最后一个下标if (visited.has(position)) return false; // 如果已经访问过，返回 falsevisited.add(position); // 标记为已访问const furthestJump = Math.min(position + nums[position], nums.length - 1);for (let i = position + 1; i <= furthestJump; i++) {if (dfs(i, nums, visited)) {return true; // 如果可以到达最后一个下标，返回 true}}return false; // 如果所有路径都不可达，返回 false
}

讲解
可以递归地尝试从当前位置跳跃到所有可能的下一个位置，直到达到最后一个下标或者确认无法到达。

1. visited 数组：用于标记已经访问过的下标，以避免重复计算。
2. dfs 函数：这是一个递归函数，接受当前下标 index 作为参数。
   • 如果 index 超过或等于最后一个下标，返回 true。
   • 如果当前下标已经访问过，返回 false。
   • 标记当前下标为已访问后，获取当前下标的最大跳跃长度 maxJump。
   • 遍历从 1 到 maxJump 的所有可能跳跃，递归调用 dfs。
   • 如果在任何跳跃中能够到达最后一个下标，返回 true。
   • 如果所有可能的跳跃都无法到达最后一个下标，返回 false。