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, 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

思路

一道很有意思的题目，最开始没有思路，看了官解的一点提示，自己也很快写出来了，还是很开心的。

和之前的跳跃题目一样，大的框架还是深搜，不过这里要求最多访问的下标数，还涉及到了DP的状态转移。

用表示从位置开始跳，可以访问的下标数。对于位置可以跳到的任何一个位置，有转移方程#card=math&code=dp%5Bi%5D%20%3D%20Math.max%28dp%5Bi%5D%2C%20dp%5Bj%5D%20%2B%201%29&id=t38bD)。而要求，同样要求可以跳到的位置的值，那么就形成了递归。

具体的代码说明见代码注释。

代码

自顶向下DFS+记忆化

class Solution {
    public int maxJumps(int[] arr, int d) {
        int ans = 0;
        int n = arr.length;
        int[] mem = new int[n];
        // 这里的状态定义和转移使用递归形式
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dfs(i, n, arr, d, mem));
        }
        return ans;
    }
    // dfs(start, ...)表示从start开始跳可以访问的下标数
    // mem是一个记忆化数组，mem[i]也表示从i处开始跳可以访问的下标数，加快计算
    private int dfs(int start, int n, int[] arr, int d, int[] mem) {
        // 因为要满足i和j之间的元素值都要小于arr[start] 因此需要倒着遍历
        for (int i = start - 1; i >= start - d; i--) {
            // 不满足arr[i] < arr[start]的话，[start-d, i]就不用再试了 下面循环同理
            if (i < 0 || arr[i] >= arr[start]) {
                break;
            }
            // 为初始值0表示还没有计算过，就进行递归，否则直接使用mem[i]就行
            if (mem[i] == 0) {
                mem[i] = dfs(i, n, arr, d, mem);
            }
            mem[start] = Math.max(mem[i] + 1, mem[start]);
        }
        for (int i = start + 1; i <= start + d; i++) {
            if (i >= n || arr[i] >= arr[start]) {
                break;
            }
            if (mem[i] == 0) {
                mem[i] = dfs(i, n, arr, d, mem);
            }
            mem[start] = Math.max(mem[i] + 1, mem[start]);
        }
        // 如果计算完了mem[start]还是0，表示从start跳不到任何一个位置，但是本身可以访问也算一次，改成1
        // 这个逻辑很重要，一方面是在逻辑(指上一行)上正确，另一方面不更改的话递归不会停止
        if (mem[start] == 0) {
            mem[start] = 1;
        }
        return mem[start];
    }
}

自底向上DP

可以使用记忆化的题目一般也可以用动态规划解决，反之也成立。

在上面方法中，元素值大的值取决于元素值小的，所以如果要自底向上的话，需要先从小的开始计算，小的计算完才可以算大的，所以我们另外构造一个二维数组，包含的元素值和下标，按元素值对其进行排序，然后先更新元素值小的值，状态的定义转移方程都和上面一样。

class Solution {
    public int maxJumps(int[] arr, int d) {
        int n = arr.length;
        int[][] tmp = new int[n][2];
        for (int i = 0; i < n; i++) {
            tmp[i][0] = arr[i];
            tmp[i][1] = i;
        }
        Arrays.sort(tmp, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int index = tmp[i][1];
            dp[index] = 1;
            for (int j = index - 1; j >= index - d; j--) {
                if (j < 0 || arr[j] >= arr[index]) {
                    break;
                }
                dp[index] = Math.max(dp[index], dp[j] + 1);
            }
            for (int j = index + 1; j <= index + d; j++) {
                if (j >= n || arr[j] >= arr[index]) {
                    break;
                }
                dp[index] = Math.max(dp[index], dp[j] + 1);
            }
            ans = Math.max(ans, dp[index]);
        }
        return ans;
    }
}