C++刷LeetCode（1340. 跳跃游戏 V）【记忆化搜索】

糖逗

题目描述：

1. 给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：
   
2. 
   
3. i + x&#160;，其中&#160;i + x < arr.length&#160;且&#160;0 < x <= d&#160;。
   
4. i - x&#160;，其中&#160;i - x >= 0&#160;且&#160;0 < x <= d&#160;。
   
5. 除此以外，你从下标&#160;i 跳到下标 j&#160;需要满足：arr[i] > arr[j]&#160;且 arr[i] > arr[k]&#160;，其中下标&#160;k&#160;是所有 i&#160;到 j&#160;之间的数字（更正式的，min(i, j) < k < max(i, j)）。
   
6. 
   
7. 你可以选择数组的任意下标开始跳跃。请你返回你 最多&#160;可以访问多少个下标。
   
8. 
   
9. 请注意，任何时刻你都不能跳到数组的外面。
   
10. 
    
11. &#160;
    
12. 
    
13. 示例 1：
    
14. 
    
15. 
    
16. 
    
17. 输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
    
18. 输出：4
    
19. 解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
    
20. 注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
    
21. 类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。
    
22. 示例 2：
    
23. 
    
24. 输入：arr = [3,3,3,3,3], d = 3
    
25. 输出：1
    
26. 解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。
    
27. 示例 3：
    
28. 
    
29. 输入：arr = [7,6,5,4,3,2,1], d = 1
    
30. 输出：7
    
31. 解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。
    
32. 示例 4：
    
33. 
    
34. 输入：arr = [7,1,7,1,7,1], d = 2
    
35. 输出：2
    
36. 示例 5：
    
37. 
    
38. 输入：arr = [66], d = 1
    
39. 输出：1
    
40. &#160;
    
41. 
    
42. 提示：
    
43. 
    
44. 1 <= arr.length <= 1000
    
45. 1 <= arr[i] <= 10^5
    
46. 1 <= d <= arr.length
    
47. 
    
48. 来源：力扣（LeetCode）
    
49. 链接：https://leetcode-cn.com/problems/jump-game-v
    
50. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     int len;
   
4. public:
   
5.     int currsion(vector<int>&arr, int d,  vector<int>&dp, int i){
   
6.         if(dp[i] != 0)return dp[i];
   
7.         int res = 0;
   
8.         for(int x = 1; x <= d && i - x >= 0; x++){
   
9.             if(arr[i - x] < arr[i]){
   
10.                 res = max(res, currsion(arr, d, dp, i-x));
    
11.             }else{
    
12.                 break;
    
13.             }
    
14.         }
    
15.         for(int x = 1; x <= d && i + x < len; x++){
    
16.             if(arr[i + x] < arr[i]){
    
17.                 res = max(res, currsion(arr, d, dp, i+x));
    
18.             }else{
    
19.                 break;
    
20.             }
    
21.         }
    
22.         res++;
    
23.         dp[i] = res;
    
24.         return dp[i];
    
25.     }
    
26.     int maxJumps(vector<int>& arr, int d) {
    
27.         len = arr.size();
    
28.         vector<int>dp(len, 0);
    
29.         int res = INT_MIN;
    
30.         for(int i = 0; i < len; i++){
    
31.             res = max(res, currsion(arr, d, dp, i));
    
32.         }
    
33.         return res;
    
34.     }
    
35. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -by-chen-shan-lian/