class Solution {
public:
int maximumJumps(vector<int>& nums, int target) {
}
};
6899. 达到末尾下标所需的最大跳跃次数
给你一个下标从 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原站题解
java 解法, 执行用时: 21 ms, 内存消耗: 42.7 MB, 提交时间: 2023-07-10 10:02:58
class Solution {
public static int maximumJumps(int[] nums, int target) {
int len = nums.length;
int[] dp = new int[len];
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (Math.abs(nums[j] - nums[i]) <= target){
if (dp[j] == 0 && j != 0) continue;
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp[len - 1] == 0 ? -1 : dp[len - 1];
}
}
java 解法, 执行用时: 17 ms, 内存消耗: 42.6 MB, 提交时间: 2023-07-10 10:02:33
class Solution {
public int maximumJumps(int[] nums, int target) {
int n = nums.length;
//f[j]:从位置0处跳跃到位置j处的最大跳跃次数
int[] f = new int[n];
Arrays.fill(f, -1);
f[0] = 0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]-nums[j]>=-1*target&&nums[i]-nums[j]<=target){
if(f[j]!=-1){
f[i]=Math.max(f[i],f[j]+1);
}
}
}
}
return f[n-1];
}
}
golang 解法, 执行用时: 24 ms, 内存消耗: 6.6 MB, 提交时间: 2023-07-10 10:01:43
// 递推
func maximumJumps(nums []int, target int) int {
n := len(nums)
f := make([]int, n)
for i := 1; i < n; i++ {
f[i] = math.MinInt
for j, x := range nums[:i] {
if -target <= nums[i]-x && nums[i]-x <= target {
f[i] = max(f[i], f[j]+1)
}
}
}
if f[n-1] < 0 {
return -1
}
return f[n-1]
}
func max(a, b int) int { if b > a { return b }; return a }
golang 解法, 执行用时: 28 ms, 内存消耗: 6.6 MB, 提交时间: 2023-07-10 10:01:12
func maximumJumps(nums []int, target int) int {
n := len(nums)
memo := make([]int, n)
for i := range memo {
memo[i] = -1 // -1 表示没有计算过
}
var dfs func(int) int
dfs = func(i int) int {
if i == 0 {
return 0
}
p := &memo[i]
if *p != -1 { // 之前算过了
return *p
}
res := math.MinInt
for j, x := range nums[:i] {
if -target <= nums[i]-x && nums[i]-x <= target {
res = max(res, dfs(j)+1)
}
}
*p = res // 记忆化
return res
}
ans := dfs(n - 1)
if ans < 0 {
return -1
}
return ans
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 852 ms, 内存消耗: 16.1 MB, 提交时间: 2023-07-10 10:00:49
# 递推
class Solution:
def maximumJumps(self, nums: List[int], target: int) -> int:
n = len(nums)
f = [-inf] * n
f[0] = 0
for i in range(1, n):
for j in range(i):
if -target <= nums[i] - nums[j] <= target:
f[i] = max(f[i], f[j] + 1)
return -1 if f[-1] < 0 else f[-1]
python3 解法, 执行用时: 656 ms, 内存消耗: 18.1 MB, 提交时间: 2023-07-10 10:00:33
'''
倒着跳
dfs(i): 从n-1到0的最大跳跃次数
枚举j, 则 dfs(i) = dfs(j) + 1
'''
class Solution:
def maximumJumps(self, nums: List[int], target: int) -> int:
@cache
def dfs(i: int):
if i == 0:
return 0
res = -inf
for j in range(i):
if -target <= nums[i] - nums[j] <= target:
res = max(res, dfs(j) + 1)
return res
ans = dfs(len(nums) - 1)
return -1 if ans < 0 else ans