1340. 跳跃游戏 V - 力扣（LeetCode）
1340. 跳跃游戏 V - 给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到： * i + x ，其中 i + x < arr.length 且 0 < x <= d 。 * i - x ，其中 i - x >= 0 且 0 < x <= d 。 除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i,...
还有第五关？！( °ヮ° )
思路
最开始看到这题脑子里会想能不能用栈做，一看输入规模，好像 O(n^2) 时间复杂度也可以接受。看了一眼提示后顿悟了，这题可以用动态规划。
动态规划 dp[i] 表示从 i 下标开始能跳跃的次数。
问题来了，我从哪个地方开始、按什么顺序递推呢？
-
开始的地方应当不依赖于任何其他
dp状态，符合这个要求的显然是最低的一个柱子，这样的地方p无法跳到其他任何地方，自然有dp[p]=0（只能访问自身，一次都跳不了） -
递推的时候我们只关注一个地方
i能跳到哪些更矮的地方，然后可以尝试从这些地方中跳跃次数最多的柱子上转移过来。因此递推顺序也是沿着柱子高度来的。 -
我们可以按照柱子高度对下标进行排序，顺着排序后的下标递推。
递推的过程中可以不断用 \max(\cdot) 更新最终结果。
思路
class Solution {
public:
int maxJumps(vector<int>& arr, int d) {
// 每个位置 i 可以跳到 [i-d, i+d] 区间内除 i 外的位置
// 只能跳到更低的地方，且中间其余柱子都是更低的
// 看了提示才知道是动态规划，但是从哪里开始递推呢？
// 当然是最矮的那个柱子，从矮的到高的，最矮的柱子哪都别想跳
int n=arr.size();
vector<int> idxs;
for(int i=0;i<n;i++){
idxs.emplace_back(i);
}
// 对下标按照柱子高度进行排序
sort(idxs.begin(),idxs.end(),[&](const int& a,const int& b){
return arr[a]<arr[b];
});
// dp[i] 表示从 i 开始跳，能跳跃的下标个数
int dp[n];
memset(dp,0,sizeof(dp));
// dp[idxs[0]]=0;
int res=0;
for(int i:idxs){
// 从低到高处理
// 往左、右走试试，只往更低的地方走，找到比 arr[i] 更低的柱子中能跳得最多的
for(int k=1;k<=d;k++){
if(i-k<0){
break;
}
if(arr[i-k]>=arr[i]){
break;
}
// 能走到这个柱子这里，看看能不能更新跳跃次数
dp[i]=max(dp[i],dp[i-k]+1);
}
for(int k=1;k<=d;k++){
if(i+k>=n){
break;
}
if(arr[i+k]>=arr[i]){
break;
}
// 能走到这个柱子这里，看看能不能更新跳跃次数
dp[i]=max(dp[i],dp[i+k]+1);
}
res=max(res,dp[i]);
}
// 最终要的是能访问的下标数而不是跳数，所以 +1
return res+1;
}
};
2 个帖子 - 2 位参与者
来源: LinuxDo 最新话题查看原文