题目描述
LeetCode 1340 — 跳跃游戏 V (Hard)
给你一个整数数组 arr 和一个整数 d。每一步你可以从下标 i 跳到下标 j，需要同时满足：
|i - j| <= d，即跳跃距离不能超过darr[i] > arr[j]，即只能往严格更低的位置跳arr[i] > arr[k]，其中k是i和j之间的所有下标——也就是说，中间不能有比起点更高或等高的柱子挡住视线
你可以选择数组的任意下标作为起点，同一个下标可以多次访问（但不重复计数）。请你返回最多能访问的下标个数。
示例 1：
- 输入：
arr = [6,4,14,6,8,13,9,7,10,6,12],d = 2 - 输出：
4 - 解释：从下标 10 出发，路径为 10 → 8 → 6 → 7，对应值 12 → 10 → 8 → 7。注意从下标 6 无法跳到下标 5，因为中间的下标 6 位置的值 9 比目标 13 低，但 13 > 9，13 挡住了去路。
示例 2：
- 输入：
arr = [3,3,3,3,3],d = 3 - 输出：
1 - 解释：所有值相等，无法跳到任何其他位置。
示例 3：
- 输入：
arr = [7,6,5,4,3,2,1],d = 1 - 输出：
7 - 解释：从下标 0 出发，一路向右跳到底。
约束：
1 <= arr.length <= 10001 <= arr[i] <= 10^51 <= d <= arr.length
求解思路
最直接的想法是枚举起点，然后 DFS 搜索所有可能的跳跃路径，记录最多能访问多少下标。问题在于，同一个位置可能被反复搜索——比如从高处跳到某个位置 A 之后，接下来能访问的点完全只取决于 A 自己的高度和位置，跟怎么跳过来的无关。如果不对这部分结果做缓存，指数级的重复计算在 n = 1000 时绝对会超时。
这个观察很关键：能且仅能从高处往低处跳，意味着跳跃关系天然无环。因为值严格递减，不可能跳回一个已经访问过的点，整个状态图是一个 DAG。DAG 上的最长路径问题，记忆化搜索是标准解法——dp[i] 表示从下标 i 出发能访问的最多下标数，遇到算过的直接返回，避免重复展开。
剩下的问题就是从一个位置出发，怎么枚举合法的跳转目标。向左向右各扫描最多 d 步，但有个核心约束——视线遮挡：一旦某一步遇到 arr[j] >= arr[i]，它后面的位置都被挡住了，直接 break。比如 [10, 5, 8, 3]、d = 3，从 10 往右看：5 可以跳，但 8 >= 10 不成立，所以 8 被挡住，更远处的 3 也就不可达了。
最后，因为题目允许从任意位置开始，遍历所有位置取 max(dp[i]) 即可。
解法：记忆化搜索
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
vector<int> memo(n, 0);
int max_res = 0;
for (int i = 0; i < n; ++i) {
max_res = max(max_res, dfs(arr, d, i, memo));
}
return max_res;
}
private:
int dfs(const vector<int>& arr, int d, int i, vector<int>& memo) {
if (memo[i] != 0) {
return memo[i]; // 已计算过，直接返回
}
int n = arr.size();
int res = 1; // 至少能访问自己
// 向右探索，遇到 arr[j] >= arr[i] 立刻停止
for (int j = i + 1; j <= min(n - 1, i + d); ++j) {
if (arr[j] >= arr[i]) break;
res = max(res, 1 + dfs(arr, d, j, memo));
}
// 向左探索，同理
for (int j = i - 1; j >= max(0, i - d); --j) {
if (arr[j] >= arr[i]) break;
res = max(res, 1 + dfs(arr, d, j, memo));
}
memo[i] = res;
return res;
}
};
复杂度： 时间 O(n · d)，每个位置最多计算一次，每次向左右各扫描最多 d 步；空间 O(n)，仅需 memo 数组和递归栈。
解法：自底向上 DP
记忆化搜索是自顶向下，也可以反过来：将下标按 arr 值从小到大排序，然后从低到高依次计算 dp[i]。这样处理到高处时，所有低处的 dp 值已经确定，无需递归。
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
vector<int> dp(n, 1);
vector<int> idx(n);
for (int i = 0; i < n; ++i) idx[i] = i;
// 按高度升序排列下标
sort(idx.begin(), idx.end(), [&](int a, int b) { return arr[a] < arr[b]; });
int ans = 1;
for (int i : idx) {
// 向右找更高的邻居，用当前 dp[i] 去更新它们
for (int j = i + 1; j <= min(n - 1, i + d); ++j) {
if (arr[j] >= arr[i]) break;
dp[j] = max(dp[j], dp[i] + 1);
}
// 向左同理
for (int j = i - 1; j >= max(0, i - d); --j) {
if (arr[j] >= arr[i]) break;
dp[j] = max(dp[j], dp[i] + 1);
}
ans = max(ans, dp[i]);
}
return ans;
}
两种写法本质相同，记忆化搜索更直观，自底向上则省去了递归开销。