LeetCode 1340. 跳跃游戏 V（困难）

题目描述

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

• i + x ，其中 i + x < arr.length 且 0 < x <= d 。
• i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：

输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：

输入：arr = [66], d = 1
输出：1

提示：

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 10^5
• 1 <= d <= arr.length

---

问题分析

这道题是跳跃游戏系列的第五题，有以下特点：

• 跳跃规则：
  • 可以向左或向右跳跃，跳跃距离范围是 [1, d]
  • 只能从高处往低处跳（arr[i] > arr[j]）
  • 跳跃路径上的所有点都必须比起点低（arr[i] > arr[k]，对于所有 i 到 j 之间的 k）
• 目标：找出从任意起点出发，最多可以访问多少个下标。
• 关键点：
  • 可以从任意下标开始
  • 需要计算的是最大访问点数，而不是是否能到达某个特定目标

这个问题适合使用动态规划来解决，因为跳跃决策具有重叠子问题的性质。同时，由于跳跃的方向性（只能从高处跳到低处），我们可以按高度排序来确定解决问题的顺序。

---

解题思路

动态规划 + 记忆化搜索

我们可以定义 dp[i] 表示从下标 i 开始跳跃，最多可以访问的下标数量（包括起点自身）。

递推关系如下：

• 对于每个下标 i，我们尝试向左或向右跳跃距离 x（其中 1 <= x <= d）
• 如果可以跳到下标 j，那么 dp[i] = max(dp[i], 1 + dp[j])

由于跳跃方向是从高到低，我们需要确保先计算出较低位置的 dp 值，再计算较高位置的 dp 值。一种方法是使用记忆化搜索（也称为自顶向下的动态规划）。

算法步骤

• 创建一个 dp 数组，dp[i] 表示从下标 i 开始最多可以访问的下标数量
• 将所有 dp[i] 初始化为 1（至少可以访问自身）
• 使用记忆化搜索，对每个下标 i：
  • 尝试向左或向右跳跃距离 x（1 <= x <= d）
  • 检查跳跃条件：目标位置在数组范围内，且路径上所有点都比起点低
  • 如果可以跳到下标 j，则 dp[i] = max(dp[i], 1 + dp[j])
• 返回所有 dp[i] 中的最大值

---

算法过程

以示例1为例：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2

让我们跟踪从下标10开始的DFS过程（这是最优起点）：

• 初始化：
  • dp[10] = 1（至少可以访问自身）
  • 当前下标：10，对应值：12

• 尝试向左跳：
  • 检查下标10-1=9：arr[10] > arr[9] (12 > 6) ✓
    • 递归计算 dp[9]
    • dp[9] = 1（至少可以访问自身）
    • 由于没有可跳的地方，dp[9] = 1
  • 检查下标10-2=8：arr[10] > arr[8] (12 > 10) ✓
    • 递归计算 dp[8]
    • dp[8] = 1
    • 检查下标8-1=7：arr[8] > arr[7] (10 > 7) ✓
      • 递归计算 dp[7]
      • dp[7] = 1
      • 检查下标7-1=6：arr[7] > arr[6] (7 < 9) ✗ 不能跳
      • 检查下标7-2=5：超出范围(d=2)
    • 所以 dp[7] = 1
    • 更新 dp[8] = 1 + dp[7] = 2
    • 检查下标8-2=6：arr[8] > arr[6] (10 > 9) ✓
      • 已计算 dp[6] = 1（没有可跳的地方）
  • 更新 dp[8] = max(2, 1+1) = 2
  • 更新 dp[10] = max(1, 1+dp[8]) = 1+2 = 3

• 最终路径：
  • 下标10 -> 下标8 -> 下标7 -> 可能的终点（无法继续跳跃）
  • 或者 下标10 -> 下标8 -> 下标6 -> 可能的终点
  • 最多访问4个下标（包括起点10）

事实上，完整的最优路径是：10 -> 8 -> 6 -> 7，总共访问4个下标。

---

详细代码实现

Java 实现

class Solution {private int[] dp;private int[] arr;private int d;public int maxJumps(int[] arr, int d) {int n = arr.length;this.arr = arr;this.d = d;this.dp = new int[n];// 初始化dp数组，每个位置至少可以访问自身Arrays.fill(dp, -1);int maxVisited = 0;for (int i = 0; i < n; i++) {maxVisited = Math.max(maxVisited, dfs(i));}return maxVisited;}private int dfs(int i) {// 如果已经计算过，直接返回if (dp[i] != -1) {return dp[i];}// 至少可以访问自身dp[i] = 1;// 尝试向右跳for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); j++) {// 检查跳跃条件if (arr[i] <= arr[j]) {break;}// 检查路径上的所有点boolean canJump = true;for (int k = i + 1; k < j; k++) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.max(dp[i], 1 + dfs(j));}}// 尝试向左跳for (int j = i - 1; j >= Math.max(i - d, 0); j--) {// 检查跳跃条件if (arr[i] <= arr[j]) {break;}// 检查路径上的所有点boolean canJump = true;for (int k = i - 1; k > j; k--) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.max(dp[i], 1 + dfs(j));}}return dp[i];}
}

C# 实现

public class Solution {private int[] dp;private int[] arr;private int d;public int MaxJumps(int[] arr, int d) {int n = arr.Length;this.arr = arr;this.d = d;this.dp = new int[n];// 初始化dp数组for (int i = 0; i < n; i++) {dp[i] = -1;}int maxVisited = 0;for (int i = 0; i < n; i++) {maxVisited = Math.Max(maxVisited, Dfs(i));}return maxVisited;}private int Dfs(int i) {// 如果已经计算过，直接返回if (dp[i] != -1) {return dp[i];}// 至少可以访问自身dp[i] = 1;// 尝试向右跳for (int j = i + 1; j <= Math.Min(i + d, arr.Length - 1); j++) {// 检查跳跃条件if (arr[i] <= arr[j]) {break;}// 检查路径上的所有点bool canJump = true;for (int k = i + 1; k < j; k++) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.Max(dp[i], 1 + Dfs(j));}}// 尝试向左跳for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {// 检查跳跃条件if (arr[i] <= arr[j]) {break;}// 检查路径上的所有点bool canJump = true;for (int k = i - 1; k > j; k--) {if (arr[k] >= arr[i]) {canJump = false;break;}}if (canJump) {dp[i] = Math.Max(dp[i], 1 + Dfs(j));}}return dp[i];}
}

---

复杂度分析

• 时间复杂度：O(n²)，其中n是数组的长度。在最坏情况下，对于每个位置，我们需要检查最多2d个可能的跳跃目标，总时间复杂度为O(n * d)。由于d最大可达n，所以最坏情况下时间复杂度是O(n²)。

• 空间复杂度：O(n)，主要用于存储dp数组和递归调用栈。

---

优化：单调栈方法

上面的实现中，检查路径上的所有点是否都比起点低的时间复杂度是 O(d)，我们可以使用单调栈来优化这一过程，降低时间复杂度。

Java 实现

class Solution {public int maxJumps(int[] arr, int d) {int n = arr.length;int[] dp = new int[n];Arrays.fill(dp, -1);// 将下标按照高度排序，从低到高处理Integer[] indices = new Integer[n];for (int i = 0; i < n; i++) {indices[i] = i;}Arrays.sort(indices, (a, b) -> arr[a] - arr[b]);int maxVisited = 0;for (int idx : indices) {maxVisited = Math.max(maxVisited, dfs(arr, d, idx, dp));}return maxVisited;}private int dfs(int[] arr, int d, int i, int[] dp) {if (dp[i] != -1) {return dp[i];}dp[i] = 1; // 至少可以访问自身// 向右跳for (int j = i + 1; j <= Math.min(i + d, arr.length - 1); j++) {if (arr[i] > arr[j]) {dp[i] = Math.max(dp[i], 1 + dfs(arr, d, j, dp));}// 如果遇到更高或相等的点，则无法继续向右if (arr[j] >= arr[i]) {break;}}// 向左跳for (int j = i - 1; j >= Math.max(i - d, 0); j--) {if (arr[i] > arr[j]) {dp[i] = Math.max(dp[i], 1 + dfs(arr, d, j, dp));}// 如果遇到更高或相等的点，则无法继续向左if (arr[j] >= arr[i]) {break;}}return dp[i];}
}

C#实现

public class Solution {public int MaxJumps(int[] arr, int d) {int n = arr.Length;int[] dp = new int[n];// 初始化dp数组，所有值设为-1表示未计算for (int i = 0; i < n; i++) {dp[i] = -1;}// 将下标按照高度排序，从低到高处理int[] indices = new int[n];for (int i = 0; i < n; i++) {indices[i] = i;}Array.Sort(indices, (a, b) => arr[a] - arr[b]);int maxVisited = 0;foreach (int idx in indices) {maxVisited = Math.Max(maxVisited, Dfs(arr, d, idx, dp));}return maxVisited;}private int Dfs(int[] arr, int d, int i, int[] dp) {// 如果已经计算过，直接返回if (dp[i] != -1) {return dp[i];}// 至少可以访问自身dp[i] = 1;// 向右跳for (int j = i + 1; j <= Math.Min(i + d, arr.Length - 1); j++) {if (arr[i] > arr[j]) {dp[i] = Math.Max(dp[i], 1 + Dfs(arr, d, j, dp));}// 如果遇到更高或相等的点，则无法继续向右if (arr[j] >= arr[i]) {break;}}// 向左跳for (int j = i - 1; j >= Math.Max(i - d, 0); j--) {if (arr[i] > arr[j]) {dp[i] = Math.Max(dp[i], 1 + Dfs(arr, d, j, dp));}// 如果遇到更高或相等的点，则无法继续向左if (arr[j] >= arr[i]) {break;}}return dp[i];}
}

---

复杂度分析

• 时间复杂度：O(n log n + n * d)
  • 排序下标需要O(n log n)时间
  • 对于每个位置，我们最多检查2d个可能的跳跃目标，总共n个位置，所以是O(n * d)
  • 综合起来就是O(n log n + n * d)

• 空间复杂度：O(n)
  • 主要用于存储dp数组、排序后的下标数组和递归调用栈

---

优化与技巧

1. 按高度排序处理：先计算高度较低的点的dp值，再计算高度较高的点的dp值，可以减少重复计算。
2. 提前终止：如果遇到高度大于等于当前点的位置，可以提前终止搜索，因为无法跳过这个位置。
3. 记忆化搜索：使用dp数组存储已计算的结果，避免重复计算。
4. 边界检查：确保跳跃不会超出数组范围。
5. 利用问题特性：由于只能从高处跳到低处，整个跳跃路径形成了一个有向无环图(DAG)，这使得动态规划可以正确解决此问题。