跳格子3问题

一、题目描述小明和朋友们一起玩跳格子游戏每个格子上有特定的分数score [1 -1-6 7 -17 7]从起点score[0]开始每次最大的步长为k请你返回小明跳到终点score[n-1]时能得到的最大得分。注1、格子的总长度和步长的区间在[1100000]2、每个格了的分数在[-10000,10000]区间中二、输入输出描述输入描述第一行格子总数第二行每个格子的分数第三行最大步长k。输出描述一个整数表示从起点跳到终点能获得的最大得分。三、示例输入61 -1 -6 7 -17 72输出14说明四、解题思路1. 核心思想动态规划DP 单调队列优化用dp[i]表示到达i的最大得分转移需要前 k 个 dp 值的最大值用单调递减队列在 O (1) 时间获取窗口最大值把复杂度从 O (nk) 优化到 O (n)2. 问题本质分析这是一个带窗口限制的动态规划问题状态转移dp[i] max(dp[i-k ... i-1]) score[i]约束只能从前面最多 k 个位置跳过来目标求dp[n-1]最后一格的最大得分本质滑动窗口最大值 DP 递推3. 核心逻辑DP 定义dp[i] 到达第i格的最大总分DP 转移只能从i-k~i-1跳过来取这段区间的最大 dp 值 当前格子分数单调队列优化队列存下标dp 值单调递减队首永远是窗口内最大值超出窗口、比当前值小的元素及时移除最终答案 dp[n-1]4. 步骤拆解输入与初始化读取格子数、分数、最大跳跃步数 k初始化 dp 数组与单调队列遍历每个格子清除队首超出跳跃范围的元素用队首最大值计算 dp [i]维护队列单调递减将当前下标加入队列输出结果输出最后一个位置的最大得分五、代码实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] score new int[n]; for (int i 0; i n; i) { score[i] sc.nextInt(); } int k sc.nextInt(); long[] dp new long[n]; dp[0] score[0]; // 单调队列存储下标对应 dp 值递减 DequeInteger q new ArrayDeque(); q.offer(0); for (int i 1; i n; i) { // 移除窗口外的元素超过 k 步 while (!q.isEmpty() q.peek() i - k) { q.poll(); } // 前面窗口最大值 当前分数 dp[i] dp[q.peek()] score[i]; // 维护队列递减比 dp[i] 小的都没用 while (!q.isEmpty() dp[i] dp[q.peekLast()]) { q.pollLast(); } q.offer(i); } System.out.println(dp[n - 1]); } }