给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 `[i + 1， min(n

1, i + k)]` 包含两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的得分为经过的所有数字之和。

请你返回你能得到的 最大得分 。

示例 1：

**输入：** nums = [ **1** , **-1** ,-2, **4** ,-7, **3** ], k = 2
**输出：** 7
**解释：** 你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

示例 2：

**输入：** nums = [ **10** ,-5,-2, **4** ,0, **3** ], k = 3
**输出：** 17
**解释：** 你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。

示例 3：

**输入：** nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
**输出：** 0

提示：

1 <= nums.length, k <= 105
-104 <= nums[i] <= 104

前言

这道题要求从下标 0 开始跳跃，每次最多跳 k 个单位，最后到达下标 n - 1，得分为经过的所有数字之和，计算最大得分。问题等价于在数组中寻找一个以下标 0 开始、以下标 n - 1 结束且相邻下标之差不超过 k 的子序列，子序列的得分为子序列的元素之和，计算最大得分。由于子序列的得分取决于子序列的最后一个元素与其余元素之和，因此可以使用动态规划计算最大得分。

数组 nums 的长度是 n。创建长度为 n 的数组 dp，其中 dp}[i] 为以下标 0 开始、以下标 i 结束且相邻下标之差不超过 k 的子序列的最大得分。

当 i = 0 时，子序列只有一个元素，得分为 nums}[0]，因此动态规划的边界情况是 dp}[0] = \textit{nums}[0]。

当 i \ge 1 时，以下标 i 结束的子序列至少有两个元素，将子序列中的除了 nums}[i] 以外的最后一个元素记为 nums}[j]，则 0 \le j < i 且 i - j \le k，当下标 j 确定时，以下标 i 结束的子序列的最大得分是 dp}[j] + \textit{nums}[i]。为了计算以下标 i 结束的子序列的最大得分，需要遍历所有符合要求的下标 j。因此动态规划的状态转移方程是：对于所有满足 0 \le j < i 且 i - j \le k 的下标 j，dp}[i] = \max{\textit{dp}[j]} + \textit{nums}[i]。

由于每一项依赖于之前的项，因此应从小到大遍历每个 i 并计算 dp}[i]。计算得到 dp}[n - 1] 即为从下标 0 跳跃到下标 n - 1 的最大得分。

对于每个 1 \le i < n 计算 dp}[i] 时，如果直接遍历所有符合要求的下标 j，则每个状态的计算时间是 O(k)，因此时间复杂度是 O(nk)，该时间复杂度过高，需要优化。

有两种优化方式，分别是优先队列和单调队列。

解法一

思路和算法

根据动态规划的状态转移方程，对于每个 1 \le i < n 计算 dp}[i] 时，需要在所有满足 0 \le j < i 且 i - j \le k 的下标 j 中寻找 dp}[j] 的最大值。可以使用优先队列维护已经计算过的状态值，为了排除与当前下标距离过大的下标，优先队列需要同时维护已经计算过的每个状态值与对应下标，优先队列的队首元素为已经计算过的最大状态值与对应下标。

首先计算 dp}[0] = \textit{nums}[0]，将状态值 dp}[0] 与下标 0 加入优先队列，然后从小到大遍历 1 \le i < n 的每个下标，对于下标 i 执行如下操作。

如果优先队列的队首元素对应的下标小于 i - k，则将优先队列的队首元素取出，重复该过程直到优先队列的队首元素对应下标大于等于 i - k。
此时优先队列的队首元素对应的状态值为所有满足 0 \le j < i 且 i - j \le k 的下标 j 中的 dp}[j] 的最大值，将 dp}[i] 的值更新为优先队列的队首元素对应的状态值与 nums}[i] 之和。
将状态值 dp}[i] 与下标 i 加入优先队列。

遍历结束之后，dp}[n - 1] 即为从下标 0 跳跃到下标 n - 1 的最大得分。

代码

[sol1-Java]class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);
        pq.offer(new int[]{dp[0], 0});
        for (int i = 1; i < n; i++) {
            while (pq.peek()[1] < i - k) {
                pq.poll();
            }
            dp[i] = pq.peek()[0] + nums[i];
            pq.offer(new int[]{dp[i], i});
        }
        return dp[n - 1];
    }
}

[sol1-C#]public class Solution {
    public int MaxResult(int[] nums, int k) {
        int n = nums.Length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();
        pq.Enqueue(new int[]{dp[0], 0}, -dp[0]);
        for (int i = 1; i < n; i++) {
            while (pq.Peek()[1] < i - k) {
                pq.Dequeue();
            }
            dp[i] = pq.Peek()[0] + nums[i];
            pq.Enqueue(new int[]{dp[i], i}, -dp[i]);
        }
        return dp[n - 1];
    }
}

复杂度分析

时间复杂度：O(n \log n)，其中 n 是数组 nums 的长度。状态数是 O(n)，每个状态值与对应下标最多加入优先队列和从优先队列中取出各一次，每次优先队列操作的时间是 O(\log n)，因此时间复杂度是 O(n \log n)。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。动态规划需要创建长度为 n 的数组 dp，优先队列中的元素个数不会超过 n。

解法二

思路和算法

根据动态规划的状态转移方程，对于每个 1 \le i < n 计算 dp}[i] 时，需要在所有满足 0 \le j < i 且 i - j \le k 的下标 j 中寻找 dp}[j] 的最大值。可以使用单调队列维护已经计算过的状态值，为了排除与当前下标距离过大的下标，单调队列需要同时维护已经计算过的每个状态值与对应下标，单调队列满足从队首到队尾的下标对应的状态值单调递减。

首先计算 dp}[0] = \textit{nums}[0]，将状态值 dp}[0] 与下标 0 入队列，然后从小到大遍历 1 \le i < n 的每个下标，对于下标 i 执行如下操作。

如果单调队列的队首元素对应的下标小于 i - k，则将单调队列的队首元素取出，重复该过程直到单调队列的队首元素对应下标大于等于 i - k。
此时单调队列的队首元素对应的状态值为所有满足 0 \le j < i 且 i - j \le k 的下标 j 中的 dp}[j] 的最大值，将 dp}[i] 的值更新为单调队列的队首元素对应的状态值与 nums}[i] 之和。
如果队列不为空且队尾元素对应的状态值小于等于 dp}[i]，则将队尾元素出队列，重复该操作直到队列为空或者队尾元素对应的状态值大于 dp}[i]。
将状态值 dp}[i] 与下标 i 在队尾入队列。

遍历结束之后，dp}[n - 1] 即为从下标 0 跳跃到下标 n - 1 的最大得分。

代码

[sol2-Java]class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        Deque<int[]> queue = new ArrayDeque<int[]>();
        queue.offerLast(new int[]{dp[0], 0});
        for (int i = 1; i < n; i++) {
            while (queue.peekFirst()[1] < i - k) {
                queue.pollFirst();
            }
            dp[i] = queue.peekFirst()[0] + nums[i];
            while (!queue.isEmpty() && queue.peekLast()[0] <= dp[i]) {
                queue.pollLast();
            }
            queue.offerLast(new int[]{dp[i], i});
        }
        return dp[n - 1];
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。状态数是 O(n)，每个状态值与对应下标最多入队列和出队列各一次，因此时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。动态规划需要创建长度为 n 的数组 dp，单调队列中的元素个数不会超过 n。

拓展问题

问题描述

原始问题只有计算最大得分，在原始问题的基础上，可以提出拓展问题：当得分最大时，应分别经过哪些下标？如果有多种方案，返回其中任意一种。

解法分析

为了计算经过的所有下标，需要在计算最大得分的过程中维护每个下标的前一个下标。

根据动态规划的状态转移方程，计算每个状态值时可以知道该状态值从哪一个状态值计算得到。

创建长度为 n 的数组 prevIndices，其中 prevIndices}[i] 为到达下标 i 的前一个下标，初始时 prevIndices 中的所有值为 -1。动态规划的计算过程中，如果 dp}[i] 从 dp}[j] 计算得到，则 prevIndices}[i] = j。

计算得到动态规划的所有状态值之后，从下标 n - 1 开始反向计算经过的所有下标。用 index 表示当前下标，初始时 index} = n - 1，每次将 index 添加到结果列表中，然后将 index 的值更新为 prevIndices}[\textit{index}]，直到 index} < 0 时结束。将结果列表反转，即可得到从起点到终点经过的所有下标。

代码

下面的代码为解法一对应的实现，返回值是一个列表，包含从起点到终点经过的所有下标。

[sol3_1-Java]class Solution {
    public List<Integer> maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int[] prevIndices = new int[n];
        Arrays.fill(prevIndices, -1);
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);
        pq.offer(new int[]{dp[0], 0});
        for (int i = 1; i < n; i++) {
            while (pq.peek()[1] < i - k) {
                pq.poll();
            }
            dp[i] = pq.peek()[0] + nums[i];
            prevIndices[i] = pq.peek()[1];
            pq.offer(new int[]{dp[i], i});
        }
        List<Integer> indices = new ArrayList<Integer>();
        int index = n - 1;
        while (index >= 0) {
            indices.add(index);
            index = prevIndices[index];
        }
        Collections.reverse(indices);
        return indices;
    }
}

[sol3_1-C#]public class Solution {
    public IList<int> MaxResult(int[] nums, int k) {
        int n = nums.Length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int[] prevIndices = new int[n];
        Array.Fill(prevIndices, -1);
        PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();
        pq.Enqueue(new int[]{dp[0], 0}, -dp[0]);
        for (int i = 1; i < n; i++) {
            while (pq.Peek()[1] < i - k) {
                pq.Dequeue();
            }
            dp[i] = pq.Peek()[0] + nums[i];
            prevIndices[i] = pq.Peek()[1];
            pq.Enqueue(new int[]{dp[i], i}, -dp[i]);
        }
        IList<int> indices = new List<int>();
        int index = n - 1;
        while (index >= 0) {
            indices.Add(index);
            index = prevIndices[index];
        }
        ((List<int>) indices).Reverse();
        return indices;
    }
}

下面的代码为解法二对应的实现，返回值是一个列表，包含从起点到终点经过的所有下标。

[sol3_2-Java]class Solution {
    public List<Integer> maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int[] prevIndices = new int[n];
        Arrays.fill(prevIndices, -1);
        Deque<int[]> queue = new ArrayDeque<int[]>();
        queue.offerLast(new int[]{dp[0], 0});
        for (int i = 1; i < n; i++) {
            while (queue.peekFirst()[1] < i - k) {
                queue.pollFirst();
            }
            dp[i] = queue.peekFirst()[0] + nums[i];
            prevIndices[i] = queue.peekFirst()[1];
            while (!queue.isEmpty() && queue.peekLast()[0] <= dp[i]) {
                queue.pollLast();
            }
            queue.offerLast(new int[]{dp[i], i});
        }
        List<Integer> indices = new ArrayList<Integer>();
        int index = n - 1;
        while (index >= 0) {
            indices.add(index);
            index = prevIndices[index];
        }
        Collections.reverse(indices);
        return indices;
    }
}

复杂度分析

时间复杂度：O(n \log n) 或 O(n)，其中 n 是数组 nums 的长度。动态规划计算最大得分的时间是 O(n \log n) 或 O(n)，计算经过的所有下标的时间是 O(n)，因此和原始问题解法的时间复杂度相同。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。需要创建长度为 n 的数组 prevIndices，因此和原始问题解法的空间复杂度相同。

1696-跳跃游戏 VI

前言

解法一

思路和算法

代码

复杂度分析

解法二

思路和算法

代码

复杂度分析

拓展问题

问题描述

解法分析

代码

复杂度分析