1.跳跃游戏（55-中）
题目描述：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
思路：本题只是问是否能达到最后一个下标。最优解贪心：计算每个位置最大的覆盖范围，看能否覆盖最后一个位置，维护一个变量记录最大覆盖位置，遍历数组即可。
注意：遍历范围为最大覆盖范围（不断更新），而不是数组的每个位置！！！
代码：
public boolean canJump(int[] nums) { int n = nums.length; int cover = 0; for (int i = 0; i <= cover; i++) { cover = Math.max(cover, i + nums[i]); if (cover >= n - 1) { return true; } } return false; }
2.跳跃游戏II（45-中）
题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例：
输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
思路：与上一题不同，本题目标是：覆盖最后一个位置的最少跳跃次数。
贪心策略：下一次跳跃在上次能跳到的范围（end）内选择一个能跳的最远的位置作为下次的起跳点 ！
注意：在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
代码：
public int jump(int[] nums) { int n = nums.length; int end = 0, maxCover = 0; int cnt = 0; for (int i = 0; i < n - 1; i++) { maxCover = Math.max(maxCover, i + nums[i]); // 到达上一次最大跳跃的右边界 if (i == end) { end = maxCover; cnt++; } } return cnt; }
3.跳跃游戏III（1306-中）
题目描述：这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]位置。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。注意，不管是什么情况下，你都无法跳到数组之外。
示例：
输入：arr = [4,2,3,0,3,1,2], start = 5 输出：true 解释： 到达值为 0 的下标 3 有以下可能方案： 下标 5 -> 下标 4 -> 下标 1 -> 下标 3 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
思路：使用递归进行求解，dfs。
- 定义一个访问数组，标记该位置是否遍历过。如果当前节点没访问过，标记为true。如果下一次再访问该点说明进入了循环，直接返回false；
- 递归终止条件：索引越界，返回false；跳到目标值，返回true
- 递归基本逻辑如题意所述。
代码：
public boolean canReach(int[] arr, int start) { int n = arr.length; boolean[] visit = new boolean[n]; return dfs(visit, arr, start); } public boolean dfs(boolean[] visit, int[] arr, int start) { if (start < 0 || start >= arr.length) { return false; } if (arr[start] == 0) { return true; } // 排除重复循环问题 if (visit[start]) { return false; } else { visit[start] = true; } return dfs(visit, arr, start + arr[start]) || dfs(visit, arr, start - arr[start]); }
4.跳跃游戏IV（1696-中）
题目描述：给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例：
输入：nums = [1,-1,-2,4,-7,3], k = 2 输出：7 解释：你可以选择子序列 [1,-1,4,3] ，和为 7 。
思路：很显然本题考查动态规划，我们用dp[i]表示以第i个元素结尾的最大得分，那么很明显，每次我们只需要找到dp[i - 1]、dp[i - 2]、...、dp[i - k]的最大值，然后加上当前元素的大小，就可以得到dp[i]。但是超时。
我们每次都要与前面的值进行比较，比较消耗性能，其实我们只需要之前的最大值。这个过程可以使用优先队列（T239滑动窗口的最大值）进行优化：双端队列queue保存滑动窗口中的最大值索引的同时，把最大值索引的【候补】也装进来。
- 新的索引i对应的得分dp[i - 1]大于队尾对应数值的元素dp[tail]，循环弹出队内元素，否则直接入队。
- 如果队列头是否已经失效，失效直接弹出队头
- 记录这时的最大值（最大得分）
代码：
// 动态规划：超时 public int maxResult(int[] nums, int k) { int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MIN_VALUE); // dp[i]:以i结尾的最大得分 dp[0] = nums[0]; for (int i = 1; i < n; ++i) { for (int j = Math.max(0, i - k); j < i; ++j) { dp[i] = Math.max(dp[i], dp[j]); } dp[i] += nums[i]; } return dp[n - 1]; } // 优先队列优化 public int maxResult(int[] nums, int k) { int n = nums.length; Deque<Integer> queue = new LinkedList<>(); int[] dp = new int[n]; dp[0] = nums[0]; for (int i = 1; i < n; ++i) { while (!queue.isEmpty() && dp[i - 1] >= dp[queue.peekLast()]) { queue.pollLast(); } queue.addLast(i - 1); // 索引不符合步数范围 if (queue.peekFirst() < i - k) { queue.pollFirst(); } dp[i] = dp[queue.peekFirst()] + nums[i]; } return dp[n - 1]; }
