题目描述
给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。
你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：
0 <= i < j < n-target <= nums[j] - nums[i] <= target
返回到达下标 n - 1 处所需的 最大跳跃次数 。
如果无法到达下标 n - 1 ，返回 -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 。
示例 2：
输入：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 。
示例 3：
输入：nums = [1,3,6,4,1,2], target = 0
输出：-1
解释：可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。
提示：
2 <= nums.length == n <= 1000-109 <= nums[i] <= 1090 <= target <= 2 * 109
解法
方法一：记忆化搜索
对于每个位置 $i$，我们考虑向后搜索能跳到的位置 $j$，如果满足 $|nums[i] - nums[j]| \leq target$，那么我们就可以从 $i$ 跳到 $j$，并且从 $j$ 开始继续向后搜索。
因此，我们设计一个函数 $dfs(i)$，表示从位置 $i$ 开始跳跃到末尾下标所需的最大跳跃次数。那么答案就是 $dfs(0)$。
函数 $dfs(i)$ 的计算过程如下：
- 如果 $i = n - 1$，那么我们已经到达了末尾下标，不需要跳跃，因此返回 $0$；
- 否则，我们需要枚举从位置 $i$ 开始能跳到的位置 $j$，并计算从 $j$ 开始跳跃到末尾下标所需的最大跳跃次数，那么 $dfs(i)$ 就等于所有 $dfs(j)$ 中的最大值加 $1$。如果不存在从 $i$ 开始能跳到的位置 $j$，那么 $dfs(i) = -\infty$。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def maximumJumps(self, nums: List[int], target: int) -> int:
@cache
def dfs(i: int) -> int:
if i == n - 1:
return 0
ans = -inf
for j in range(i + 1, n):
if abs(nums[i] - nums[j]) <= target:
ans = max(ans, 1 + dfs(j))
return ans
n = len(nums)
ans = dfs(0)
return -1 if ans < 0 else ans
|
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 | class Solution {
private Integer[] f;
private int[] nums;
private int n;
private int target;
public int maximumJumps(int[] nums, int target) {
n = nums.length;
this.target = target;
this.nums = nums;
f = new Integer[n];
int ans = dfs(0);
return ans < 0 ? -1 : ans;
}
private int dfs(int i) {
if (i == n - 1) {
return 0;
}
if (f[i] != null) {
return f[i];
}
int ans = -(1 << 30);
for (int j = i + 1; j < n; ++j) {
if (Math.abs(nums[i] - nums[j]) <= target) {
ans = Math.max(ans, 1 + dfs(j));
}
}
return f[i] = ans;
}
}
|
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 | class Solution {
public:
int maximumJumps(vector<int>& nums, int target) {
int n = nums.size();
int f[n];
memset(f, -1, sizeof(f));
function<int(int)> dfs = [&](int i) {
if (i == n - 1) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
f[i] = -(1 << 30);
for (int j = i + 1; j < n; ++j) {
if (abs(nums[i] - nums[j]) <= target) {
f[i] = max(f[i], 1 + dfs(j));
}
}
return f[i];
};
int ans = dfs(0);
return ans < 0 ? -1 : ans;
}
};
|
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 | func maximumJumps(nums []int, target int) int {
n := len(nums)
f := make([]int, n)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i == n-1 {
return 0
}
if f[i] != -1 {
return f[i]
}
f[i] = -(1 << 30)
for j := i + 1; j < n; j++ {
if abs(nums[i]-nums[j]) <= target {
f[i] = max(f[i], 1+dfs(j))
}
}
return f[i]
}
ans := dfs(0)
if ans < 0 {
return -1
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | function maximumJumps(nums: number[], target: number): number {
const n = nums.length;
const f: number[] = Array(n).fill(-1);
const dfs = (i: number): number => {
if (i === n - 1) {
return 0;
}
if (f[i] !== -1) {
return f[i];
}
f[i] = -(1 << 30);
for (let j = i + 1; j < n; ++j) {
if (Math.abs(nums[i] - nums[j]) <= target) {
f[i] = Math.max(f[i], 1 + dfs(j));
}
}
return f[i];
};
const ans = dfs(0);
return ans < 0 ? -1 : ans;
}
|