题目描述
给你一个下标从 0 开始、由 n
个整数组成的数组 nums
和一个整数 target
。
你的初始位置在下标 0
。在一步操作中,你可以从下标 i
跳跃到任意满足下述条件的下标 j
:
0 <= i < j < n
-target <= nums[j] - nums[i] <= target
返回到达下标 n - 1
处所需的 最大跳跃次数。
如果无法到达下标 n - 1
,返回 -1
。
样例
输入:nums = [1,3,6,4,1,2], target = 2
输出:3
解释:要想以最大跳跃次数从下标 0 到下标 n - 1,可以按下述跳跃序列执行操作:
- 从下标 0 跳跃到下标 1。
- 从下标 1 跳跃到下标 3。
- 从下标 3 跳跃到下标 5。
可以证明,从 0 到 n - 1 的所有方案中,不存在比 3 步更长的跳跃序列。因此,答案是 3。
输入:nums = [1,3,6,4,1,2], target = 3
输出:5
解释:要想以最大跳跃次数从下标 0 到下标 n - 1,可以按下述跳跃序列执行操作:
- 从下标 0 跳跃到下标 1。
- 从下标 1 跳跃到下标 2。
- 从下标 2 跳跃到下标 3。
- 从下标 3 跳跃到下标 4。
- 从下标 4 跳跃到下标 5。
可以证明,从 0 到 n - 1 的所有方案中,不存在比 5 步更长的跳跃序列。因此,答案是 5。
输入:nums = [1,3,6,4,1,2], target = 0
输出:-1
解释:可以证明不存在从 0 到 n - 1 的跳跃序列。因此,答案是 -1。
限制
2 <= nums.length == n <= 1000
-10^9 <= nums[i] <= 10^9
0 <= target <= 2 * 10^9
算法
(动态规划) $O(n^2)$
- 设状态 $f(i)$ 表示以 $i$ 为结尾的最大跳跃次数,如果无法到达,则为负无穷。
- 初始时,$f(0) = 0$,其他为负无穷待定。
- 转移时,对于 $f(i)$,枚举 $0 \le j < i$,当满足 $|nums[i] - nums[j]| \le target$ 时,转移 $f(i) = \max(f(i), f(j) + 1)$。
- 最终答案为 $f(n - 1)$。如果答案为负无穷,则返回 $-1$。
时间复杂度
- 状态数为 $O(n)$,转移时间为 $O(n)$,时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储状态。
C++ 代码
class Solution {
public:
int maximumJumps(vector<int>& nums, int target) {
const int n = nums.size();
vector<int> f(n, INT_MIN);
f[0] = 0;
for (int i = 1, j = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (abs(nums[i] - nums[j]) <= target)
f[i] = max(f[i], f[j] + 1);
if (f[n - 1] < 0)
return -1;
return f[n - 1];
}
};