2770. 达到末尾下标所需的最大跳跃次数 - 力扣（LeetCode）
2770. 达到末尾下标所需的最大跳跃次数 - 给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。 你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ： * 0 <= i < j < n * -target <= nums[j] - nums[i] <= target 返回到达下标 n - 1 处所需的 最大跳跃次数 。 如果无法到达下标 n - 1 ，返回 -1 。 示例...
思路
注意是求最大的跳跃次数。
题目条件：
- 每一步只能往后跳；
- 且跳转后的值和当前值的差的绝对值要在
[0, target]范围内。
对于每个位置，我可能从前面每个满足上述条件的位置转移过来，因此对于每个位置存储其状态【到达这个位置所需的最大跳跃次数】，然后递推即可。
因此很明显是一道一维动态规划题。
代码
class Solution {
public:
int maximumJumps(vector<int>& nums, int target) {
// 每一步只能往后跳
// 且跳到的值和当前值的差的绝对值要在 [0, target] 区间
// 注意这题找的是**最大**跳跃次数
// 应该是能用动态规划的
int n=nums.size();
// dp[i] 表示从 0 下标跳到 i 需要的最大跳跃次数
int dp[n];
dp[0]=0; // 显然 0 跳到 0 最大跳跃次数就是 0
for(int j=1;j<n;j++){
dp[j]=-1;
for(int i=0;i<j;i++){
if(dp[i]==-1){
// 如果 dp[i] 没法跳到就跳过
continue;
}
int sub=nums[j]-nums[i];
if(-target<=sub&&sub<=target){
// 可以从 i 跳到 j，则看看能不能更新到 j 的最大跳跃次数
dp[j]=max(dp[j],dp[i]+1);
}
}
}
return dp[n-1];
}
};
2 个帖子 - 2 位参与者
来源: LinuxDo 最新话题查看原文