2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《跳格子3》：

---

---

题目名称：跳格子3

---

属性	内容
知识点	动态规划、滑动窗口优化
时间限制	1秒
空间限制	256MB
限定语言	不限

---

题目描述

小明和朋友们玩跳格子游戏，每个格子有特定分数 score = [1, -1, -6, 7, -17, 7]。从起点 score[0] 开始，每次最大跳跃步长为 k，求跳到终点 score[n-1] 时的最大得分。

输入描述

• 第一行输入整数 n（1 ≤ n ≤ 1e5）。
• 第二行输入 n 个整数表示 score[i]（-1e4 ≤ score[i] ≤ 1e4）。
• 第三行输入整数 k（1 ≤ k ≤ 1e5）。

输出描述
输出一个整数，表示最大得分。

示例
输入：

6  
1 -1 -6 7 -17 7  
2  

输出：

14  

解释：路径为 0 → 1 → 3 → 5，得分为 1 + (-1) + 7 + 7 = 14。

---

Java

问题分析

我们需要找到从起点跳到终点（每个格子有特定分数）的最大得分，每次跳跃步长不超过k。动态规划结合单调队列优化是关键。

---

解题思路

1. 动态规划定义：dp[i] 表示跳到第i个格子时的最大得分。
2. 状态转移：dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。
3. 单调队列优化：用双端队列维护窗口大小为k的区间，保证队列头部是最大值，时间复杂度优化到O(n)。

---

代码实现

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] scores = new int[n];for (int i = 0; i < n; i++) {scores[i] = scanner.nextInt();}int k = scanner.nextInt();scanner.close();if (n == 0) {System.out.println(0);return;}long[] dp = new long[n];  // 避免整数溢出dp[0] = scores[0];        // 初始化起点得分Deque<Integer> deque = new ArrayDeque<>();deque.offerLast(0);        // 初始队列存入起点索引for (int i = 1; i < n; i++) {// 移除超出窗口范围的队首元素（窗口左边界为i-k）while (!deque.isEmpty() && deque.peekFirst() < i - k) {deque.pollFirst();}// 当前最大得分 = 窗口内最大值 + 当前格子分数dp[i] = dp[deque.peekFirst()] + scores[i];// 维护队列单调递减：移除队尾所有小于当前值的元素while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);  // 将当前索引加入队列}System.out.println(dp[n - 1]);}
}

---

代码详细解析

1. 输入处理：

   • 读取n、分数数组和k。
   • 处理n=0的边界情况。

2. 动态规划数组初始化：

   • dp[0] 初始化为第一个格子的分数，因为起点必须跳到这里。

3. 双端队列初始化：

   • 队列存储索引，初始时存入0（起点）。

4. 遍历每个格子：

   • 移除窗口外元素：队列头部索引必须≥i-k，否则弹出。
   • 计算当前得分：队列头部对应窗口最大值，加上当前分数。
   • 维护队列单调性：弹出队尾所有小于当前得分的元素，保证队列递减。
   • 加入当前索引：当前索引入队，供后续计算使用。

5. 输出结果：dp[n-1] 是跳到终点的最大得分。

---

示例测试

示例输入：

6  
1 -1 -6 7 -17 7  
2  

输出：

14

解析：

• 路径为0→1→3→5，得分1 + (-1) +7 +7 =14。

另一个测试用例：

3  
3 1 5  
2  

输出：

9

解析：

• 路径为0→1→2，得分3+1+5=9。

---

综合分析

1. 时间复杂度：O(n)

   • 每个元素入队出队一次，总操作次数为O(n)，适合处理1e5数据。

2. 空间复杂度：O(n)

   • dp 数组存储每个格子的最大得分，队列最多存储k个元素。

3. 优势：

   • 单调队列优化避免了重复计算窗口最大值。
   • 逻辑清晰，代码简洁，适合处理大规模数据。

4. 适用场景：

   • 需要高效处理滑动窗口最大值的动态规划问题。
   • 适用于实时系统或高频数据处理场景。

---

python

问题分析

我们需要找到从起点跳到终点的最大得分，每次跳跃步长不超过k。动态规划结合单调队列优化可以高效解决该问题。

---

解题思路

1. 动态规划定义：dp[i] 表示跳到第i个格子时的最大得分。
2. 状态转移：dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。
3. 单调队列优化：使用双端队列维护窗口大小为k的区间，队列头部保持最大值，时间复杂度优化到O(n)。

---

代码实现

import sys
from collections import dequedef main():# 读取输入数据n = int(sys.stdin.readline())score = list(map(