题目
2770. 达到末尾下标所需的最大跳跃次数 - 力扣（LeetCode）
给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。
你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：
0 <= i < j < n-target <= nums[j] - nums[i] <= target
返回到达下标 n - 1 处所需的 最大跳跃次数 。
如果无法到达下标 n - 1 ，返回 -1 。
示例一：
代码语言：javascript复制输入：nums = [1,3,6,4,1,2], target = 2
输出：3
解释：要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：
- 从下标 0 跳跃到下标 1 。
- 从下标 1 跳跃到下标 3 。
- 从下标 3 跳跃到下标 5 。
可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。 示例二：
代码语言：javascript复制输入：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 。 示例三：
代码语言：javascript复制输入：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
解题
解法一
思路
本题同样是用到动态规划，使用动态规划可以很简单地解决问题。
首先建立一个存储每个索引处最多的到达方法dp[]，dp[i]表示到达nums[i]的最多的步数。然后用两个for循环，第一个for循环用来走nums数组，将nums数组每个索引走到的最大次数都存进dp[i]当中，第二个for循环用来看前面的索引处能不能到达第一个for循环到达的i，要是能到达，取最长的步数存入dp[i]中。
存储最大步数：dp[i] = Math.max(dp[i],dp[j] 1);
解决
代码语言：javascript复制class Solution {
public int maximumJumps(int[] nums, int target) {
int length = nums.length;
//声明dp数组，用于动态规划，dp[i]记录的是到达nums[i]的长度
int dp[] = new int[length];
//默认索引0处的方法数为1
dp[0] = 1;
for(int i=1;i=-target && dp[j]!=0){
//可达且j也是可达，然后挑选最大的路进行记录
dp[i] = Math.max(dp[i],dp[j] 1);
}
}
}
return dp[length-1]-1;
}
}结果
代码语言：javascript复制> 2023/07/17 18:33:35
解答成功:
执行耗时:15 ms,击败了95.33% 的Java用户
内存消耗:42.5 MB,击败了78.94% 的Java用户
