本文主要是介绍LeetCode：1696. 跳跃游戏 VI（DP， Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1696. 跳跃游戏 VI
题目描述：
实现代码与解析：
一眼dp（超时，后面给出优化思路和代码）
原理思路：
优化后代码：
1696. 跳跃游戏 VI
题目描述：
给你一个下标从 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
实现代码与解析：
一眼dp（超时，后面给出优化思路和代码）
class Solution {public int maxResult(int[] nums, int k) {int n = nums.length;int[] f = new int[n];Arrays.fill(f, -0x3f3f3f3f);f[0] = nums[0];for (int i = 1; i < n; i++) {int j = i - k >= 0 ? i - k : 0;for (; j < i; j++) {f[i] = Math.max(f[i], f[j] + nums[i]);}}return f[n - 1];}
}原理思路：
一眼dp，但是超时，这个dp就不用再解析了吧，简单的dp，主要是考虑优化。
很明显，我们这里在dp第二层遍历i - k 到 i 这个区间的时候，没必要都遍历下来，只需要找最大的值，所以优化思路不就来了，那这个区间，不就是滑动窗口找最大值么，双端队列。
不过我们这里是i - k 到 i - 1的区间 最大值，所以先计算然后再将当前遍历的数下标插入队列。
不懂滑动窗口可以看看我之前的文章，其实就是用来求区间的最值的，遇到这种问题直接用就行。
Leetcode：239. 滑动窗口最大值（C++）_滑动窗口最大值 c++-CSDN博客
优化后代码：
class Solution {public int maxResult(int[] nums, int k) {int n = nums.length;int[] f = new int[n];f[0] = nums[0];Deque<Integer> q = new ArrayDeque<>();q.offerLast(0);for (int i = 1; i < n; i++) {if (q.peekFirst() < i - k) { // 移动，若左端点未出队，让其出队q.pollFirst();}f[i] = nums[i] + f[q.peekFirst()]; // 计算当前位置最大值while (!q.isEmpty() && f[i] >= f[q.peekLast()]) { // 入队，单调队列q.pollLast();}q.offerLast(i); // 入队}return f[n - 1];}
}这篇关于LeetCode：1696. 跳跃游戏 VI（DP， Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
