C++刷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 > arr 且 arr > arr ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。
你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。
请注意，任何时刻你都不能跳到数组的外面。
示例 1：
输入：arr = , d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。
示例 2：
输入：arr = , d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。
示例 3：
输入：arr = , d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。
示例 4：
输入：arr = , d = 2
输出：2
示例 5：
输入：arr = , d = 1
输出：1
提示：
1 <= arr.length <= 1000
1 <= arr <= 10^5
1 <= d <= arr.length
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-v
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
int len;
public:
int currsion(vector<int>&arr, int d,vector<int>&dp, int i){
if(dp != 0)return dp;
int res = 0;
for(int x = 1; x <= d && i - x >= 0; x++){
if(arr < arr){
res = max(res, currsion(arr, d, dp, i-x));
}else{
break;
}
}
for(int x = 1; x <= d && i + x < len; x++){
if(arr < arr){
res = max(res, currsion(arr, d, dp, i+x));
}else{
break;
}
}
res++;
dp = res;
return dp;
}
int maxJumps(vector<int>& arr, int d) {
len = arr.size();
vector<int>dp(len, 0);
int res = INT_MIN;
for(int i = 0; i < len; i++){
res = max(res, currsion(arr, d, dp, i));
}
return res;
}
};
参考链接：https://leetcode-cn.com/problems/jump-game-v/solution/dfsji-yi-hua-sou-suo-ondfu-za-du-by-chen-shan-lian/
页:
[1]