题目描述：
给你一个整数数组 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\le arr.len \le 1000, 1\le arr[i] \le 10^5$
题解：
可以直接 $dp[i]$ 表示从 $i$ 开始能跳的最多下标，然后枚举 $j \in [\max(0, i - d), \min(n - 1, i + d)]$ 更新 $dp[i] = dp[j] + 1$ 。
但是枚举的时候发现，比自己小的 $arr[j]$ 可能还没有被更新过，这个地方有问题。需要调整更新顺序，因此，需要先排序，然后再一个一个更新。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
int maxJumps(vector<int> &arr, int d)
{
int n = arr.size();
vector<int> dp(n, 1);
int ans = 0;
vector<pair<int, int>> nums(n);
for (int i = 0; i < n; ++i)
{
nums[i] = {arr[i], i};
}
sort(nums.begin(), nums.end());
for (int i = 0; i < n; ++i)
{
int index = nums[i].second;
for (int j = index - 1; j >= max(0, index - d) && arr[j] < arr[index]; --j)
{
dp[index] = max(dp[index], dp[j] + 1);
}
for (int j = index + 1; j <= min(n - 1, index + d) && arr[j] < arr[index]; ++j)
{
dp[index] = max(dp[index], dp[j] + 1);
}
}
return *max_element(dp.begin(), dp.end());
}
};
|