LEETCODE 1340. Jump Game V 解题思路分析

题目大意：

跳跃游戏 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, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
 注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
 类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：

输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：

输入：arr = [66], d = 1
输出：1

提示：

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 10^5
• 1 <= d <= arr.length

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1340

解题思路分析：

这是跳跃游戏系列题目的又一续集，我们之前的文章介绍过：

LEETCODE 55. Jump Game 解题思路分析

LEETCODE 1306. Jump Game III 解题思路分析

本题解法与前两题不同，需要考虑采用动态规划或者是递归方式来解题。我们先简单复述一下题目大意，起始时，可以从任意一点开始起跳，跳跃时需要考虑两个条件，第一，每次跳跃的最大下标距离不能超过d。第二，遵循由高向低跳的原则，即当前跳跃的终点位置一定要低于起点位置，并且起点与终点之间的所有位置的高度也要低于起点位置。当无法再跳向其他任何位置为止结束当前跳跃。题目求的是经过节点数最多的一种跳跃。

由于题目没有给出最初的起跳点，因此我们需要循环尝试从每一个点开始起跳。对于每个起点，我们首先要确定它能够跳到的下个节点的取值范围。根据上文提到的跳跃条件，跳跃终点以及起点到终点间的高度都必须小于起点，因此，在起点左右d长度区间范围内，首个连续小于当前起点高度的区间为合理取值范围。对于取值范围内的所有下一个位置，我们事先无法获知跳到哪里能够对全局产生最优解，因此我们依然需要一一作出尝试。每跳到一个新的位置后，继续按照上面的逻辑取得接下来跳跃的取值范围，直到取值范围变为0为止。以上逻辑是典型的递归思想。解题时，为了避免重复计算，我们需要引入memo记忆数组，记录已经跳跃过的节点能跳跃的最大步数。

实现代码：

int[] memo; // 记忆数组，memo[i]表示从下标i开始起跳，最多能够访问的节点数
public int maxJumps(int[] arr, int d) {
    // 初始化记忆数组
    memo=new int[arr.length];
    // 返回结果，最多能够访问的节点数
    int res = 0;
    // 循环每个位置作为起始位置
    for(int i=0;i<arr.length;i++){
        // 计算当前位置起跳能够访问的最多节点
        res=Math.max(res, help(arr,d,i)+1);
    }
    return res;
}
// arr：数组
// d：每一步能跳跃的最远距离
// index：当前位置
// 返回从当前位置开始跳跃，能够访问的最多节点数
int help(int[] arr, int d, int index){
    // 返回值
    int res=0;
    // 当前位置高度
    int currnt=arr[index];
    // 如果记忆数组中存在当前位置的结果，直接返回
    if(memo[index]>0) return memo[index];
    // 下一步向左边跳跃能够达到的最远距离
    // 理论上是左边边界是index-d，但注意下标不能小于0
    int minIndex=Math.max(0,index-d);
    // 循环尝试向左边范围内的每一点跳跃
    for(int i=index-1;i>=minIndex;i--){
        // 如果左边位置高于或等于当前高度，结束左边区间循环
        if(currnt<=arr[i]) break;
        // 向左边跳到下一点（加一代表访问了当前位置）
        res=Math.max(res,help(arr,d,i)+1);
    }
    // 同理向右边跳跃
    int maxIndex=Math.min(arr.length-1,index+d);
    for(int i=index+1;i<=maxIndex;i++){
        if(currnt<=arr[i]) break;
        res=Math.max(res, help(arr,d,i)+1);
    }
    // 将从当前位置开始跳跃，能够访问的最多节点数存入记忆数组
    memo[index]=res;
    return res;
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 70.15% of Java online submissions for Jump Game V.

Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Jump Game V.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1340-jump-game-v-解题思路分析/