⭐算法OJ⭐跳跃游戏【动态规划 + 单调队列】（C++实现）Jump Game 系列 VI

⭐算法OJ⭐跳跃游戏【贪心算法】（C++实现）Jump Game 系列 I,II
⭐算法OJ⭐跳跃游戏【BFS+滑动窗口】（C++实现）Jump Game 系列 III,IIV

1696. Jump Game VI

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.

Example 1:

Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

Example 2:

Input: nums = [10,-5,-2,4,0,3], k = 3
Output: 17
Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.

Example 3:

Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output: 0

问题理解

给定一个 0 索引 的整数数组 nums 和一个整数 k。你最初站在索引 0 处。在每一次移动中，你可以向前跳跃最多 k 步，但不能跳出数组的边界。也就是说，你可以从索引 i 跳到范围 [i + 1, min(n - 1, i + k)] 内的任意索引。

你的目标是到达数组的最后一个索引（索引 n - 1）。你的得分是你访问过的所有索引 j 对应的 nums[j] 的总和。

要求返回 你能获得的最大得分。

解决思路

这是一个典型的动态规划问题。我们需要找到从索引 0 到索引 n - 1 的最大得分路径。

状态定义：
- 设 dp[i] 表示从索引 0 跳到索引 i 的最大得分。
状态转移：
- 对于每个索引 i，我们需要检查从 $[i - k, i - 1]$ 范围内的所有可能的前一个位置 j，并选择使得 dp[j] + nums[i] 最大的值。
状态转移方程为：
$d p [i] = ma x (d p [j] + n u m s [i]) 其中 j \in [i - k, i - 1]$
初始条件：dp[0] = nums[0]，因为起点是索引 0。
优化：
- 直接使用动态规划会导致时间复杂度为 $O (n \times k)$ ，对于较大的 $n$ 和 $k$ 可能无法通过。
- 可以使用单调队列（Monotonic Queue）优化，将时间复杂度降低到 $O (n)$ 。

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n); // dp[i] 表示跳到索引 i 的最大得分
    dp[0] = nums[0];   // 初始条件
    deque<int> dq;     // 单调队列，存储索引
    dq.push_back(0);   // 初始队列

    for (int i = 1; i < n; i++) {
        // 移除不在窗口范围内的索引
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }
        
        // 更新 dp[i]
        dp[i] = dp[dq.front()] + nums[i];
        
        // 维护单调队列
        while (!dq.empty() && dp[i] >= dp[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    
    return dp[n - 1]; // 返回最后一个索引的最大得分
}

代码说明

动态规划数组 dp：
- dp[i] 表示从索引 0 跳到索引 i 的最大得分。
- 初始条件：dp[0] = nums[0]。
单调队列 dq：
- 用于维护当前窗口 $[i - k, i - 1]$ 内的最大值对应的索引。
- 队列中的索引对应的 dp 值是递减的。
遍历数组：
- 对于每个索引 i，移除队列中不在窗口范围内的索引。
- 更新 dp[i] 为 dp[dq.front()] + nums[i]。
- 维护单调队列，确保队列中的索引对应的 dp 值是递减的。
返回结果：
- 最终返回 dp[n - 1]，即最后一个索引的最大得分。