2025 A卷 200分 题型
本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！
华为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。动态规划结合单调队列优化是关键。
解题思路
- 动态规划定义：
dp[i]表示跳到第i个格子时的最大得分。 - 状态转移：
dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。 - 单调队列优化：用双端队列维护窗口大小为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]);
}
}
代码详细解析
输入处理：
- 读取n、分数数组和k。
- 处理n=0的边界情况。
动态规划数组初始化：
dp[0]初始化为第一个格子的分数，因为起点必须跳到这里。
双端队列初始化：
- 队列存储索引，初始时存入0（起点）。
遍历每个格子：
- 移除窗口外元素：队列头部索引必须≥i-k，否则弹出。
- 计算当前得分：队列头部对应窗口最大值，加上当前分数。
- 维护队列单调性：弹出队尾所有小于当前得分的元素，保证队列递减。
- 加入当前索引：当前索引入队，供后续计算使用。
输出结果：
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。
综合分析
时间复杂度：O(n)
- 每个元素入队出队一次，总操作次数为O(n)，适合处理1e5数据。
空间复杂度：O(n)
dp数组存储每个格子的最大得分，队列最多存储k个元素。
优势：
- 单调队列优化避免了重复计算窗口最大值。
- 逻辑清晰，代码简洁，适合处理大规模数据。
适用场景：
- 需要高效处理滑动窗口最大值的动态规划问题。
- 适用于实时系统或高频数据处理场景。
python
问题分析
我们需要找到从起点跳到终点的最大得分，每次跳跃步长不超过k。动态规划结合单调队列优化可以高效解决该问题。
解题思路
- 动态规划定义：
dp[i]表示跳到第i个格子时的最大得分。 - 状态转移：
dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。 - 单调队列优化：使用双端队列维护窗口大小为k的区间，队列头部保持最大值，时间复杂度优化到O(n)。
代码实现
import sys
from collections import deque
def main():
# 读取输入数据
n = int(sys.stdin.readline())
score = list(map(int, sys.stdin.readline().split()))
k = int(sys.stdin.readline())
# 处理n=0的边界情况（题目保证n≥1）
if n == 0:
print(0)
return
dp = [0] * n # 初始化dp数组
dp[0] = score[0] # 起点得分
q = deque([0]) # 双端队列存储索引，保证单调递减
for i in range(1, n):
# 移除窗口外的元素（索引 < i - k）
while q and q[0] < i - k:
q.popleft()
# 计算当前格子的最大得分
dp[i] = dp[q[0]] + score[i]
# 维护队列单调递减：弹出所有小于当前值的元素
while q and dp[i] >= dp[q[-1]]:
q.pop()
q.append(i) # 当前索引入队
print(dp[-1]) # 输出终点得分
if __name__ == "__main__":
main()
代码详细解析
输入处理：
sys.stdin.readline()逐行读取输入。n为格子数量，score为分数数组，k为最大跳跃步长。
初始化变量：
dp数组：dp[i]表示跳到第i个格子的最大得分，初始化dp[0] = score[0]。- 双端队列
q：存储索引，保证队列中元素对应的dp值单调递减。
遍历每个格子：
- 移除窗口外元素：队列头部索引必须≥
i - k，否则弹出。 - 计算当前得分：队列头部对应窗口最大值，加上当前分数。
- 维护队列单调性：弹出队尾所有小于当前得分的元素。
- 索引入队：将当前索引加入队列尾部。
- 移除窗口外元素：队列头部索引必须≥
输出结果：
dp[-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。
综合分析
时间复杂度：O(n)
- 每个元素入队和出队一次，总操作次数为O(n)，适合处理1e5数据。
空间复杂度：O(n)
dp数组存储每个格子的得分，队列最多存储k个元素。
优势：
- 单调队列优化：高效维护窗口最大值，避免重复计算。
- 代码简洁：逻辑清晰，适合处理大规模数据。
适用场景：
- 需要高效处理滑动窗口最大值的动态规划问题。
- 适用于实时系统或高频数据处理场景。
JavaScript
问题分析
我们需要找到从起点跳到终点的最大得分，每次跳跃步长不超过k。动态规划结合单调队列优化可以高效解决该问题。
解题思路
- 动态规划定义：
dp[i]表示跳到第i个格子时的最大得分。 - 状态转移：
dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。 - 单调队列优化：使用双端队列维护窗口大小为k的区间，队列头部保持最大值，时间复杂度优化到O(n)。
代码实现
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal: false
});
let n; // 格子数量
let scores = []; // 每个格子的分数
let k; // 最大跳跃步长
let lineCount = 0;
rl.on('line', (line) => {
line = line.trim();
if (lineCount === 0) { // 第一行读取n
n = parseInt(line);
} else if (lineCount === 1) { // 第二行读取分数数组
scores = line.split(/\s+/).map(Number);
} else if (lineCount === 2) { // 第三行读取k
k = parseInt(line);
rl.close(); // 关闭输入流
}
lineCount++;
}).on('close', () => {
if (n === 0) { // 边界情况处理
console.log(0);
return;
}
const dp = new Array(n).fill(0); // 初始化dp数组
dp[0] = scores[0]; // 起点得分
const deque = [0]; // 双端队列（存储索引），初始放入0
for (let i = 1; i < n; i++) {
// 1. 移除超出窗口的队头元素（窗口左边界为i-k）
while (deque.length > 0 && deque[0] < i - k) {
deque.shift();
}
// 2. 计算当前格子的最大得分（窗口最大值 + 当前分数）
dp[i] = dp[deque[0]] + scores[i];
// 3. 维护队列单调递减：移除队尾所有小于当前值的元素
while (deque.length > 0 && dp[i] >= dp[deque[deque.length - 1]]) {
deque.pop();
}
deque.push(i); // 当前索引入队
}
console.log(dp[n - 1]); // 输出终点得分
});
代码详细解析
输入处理：
readline逐行读取输入。- 第一行读取格子数量
n。 - 第二行分割字符串转换为分数数组
scores。 - 第三行读取最大跳跃步长
k。
初始化变量：
dp数组：dp[i]表示跳到第i个格子的最大得分，初始化为0，dp[0]设为scores[0]。deque双端队列：初始放入索引0，表示起点。
遍历处理每个格子：
- 移除窗口外元素：若队列头部索引
< i - k，从队列头部移除。 - 计算当前得分：当前最大得分 = 队列头部索引对应的
dp值 + 当前分数。 - 维护队列单调性：从队列尾部弹出所有小于当前
dp[i]的索引。 - 索引入队：将当前索引加入队列尾部。
- 移除窗口外元素：若队列头部索引
输出结果：打印
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。
综合分析
时间复杂度：O(n)
- 每个元素入队和出队一次，总操作次数为O(n)。
空间复杂度：O(n)
dp数组存储每个格子的得分，队列最多存储k个元素。
优势：
- 单调队列优化：高效维护窗口最大值，避免重复计算。
- 逻辑清晰：代码简洁，适合处理大规模数据。
适用场景：
- 需要高效处理滑动窗口最大值的动态规划问题。
- 适用于实时系统或高频数据处理场景。
C++
问题分析
我们需要找到从起点跳到终点的最大得分，每次跳跃步长不超过k。动态规划结合单调队列优化可以高效解决该问题。
解题思路
- 动态规划定义：
dp[i]表示跳到第i个格子时的最大得分。 - 状态转移：
dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。 - 单调队列优化：使用双端队列维护窗口大小为k的区间，队列头部保持最大值，时间复杂度优化到O(n)。
代码实现
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> score(n);
for (int i = 0; i < n; ++i) {
cin >> score[i];
}
int k;
cin >> k;
vector<long long> dp(n); // 动态规划数组
dp[0] = score[0]; // 起点得分
deque<int> dq; // 双端队列维护窗口最大值索引
dq.push_back(0); // 初始放入起点索引
for (int i = 1; i < n; ++i) {
// 移除窗口外的元素（索引 < i - k）
while (!dq.empty() && dq.front() < i - k) {
dq.pop_front();
}
// 计算当前格子的最大得分
dp[i] = dp[dq.front()] + score[i];
// 维护队列单调递减：移除队尾所有小于当前值的元素
while (!dq.empty() && dp[i] >= dp[dq.back()]) {
dq.pop_back();
}
dq.push_back(i); // 当前索引入队
}
cout << dp[n - 1] << endl;
return 0;
}
代码详细解析
输入处理：
cin读取输入数据，包括格子数量n、分数数组score和最大跳跃步长k。
初始化变量：
dp数组：dp[i]表示跳到第i个格子的最大得分，初始化为dp[0] = score[0]。dq双端队列：存储索引，初始时放入起点索引0。
遍历每个格子：
- 移除窗口外元素：队列头部索引必须≥
i - k，否则弹出。 - 计算当前得分：队列头部对应窗口最大值，加上当前分数。
- 维护队列单调性：弹出队尾所有小于当前得分的元素。
- 索引入队：将当前索引加入队列尾部。
- 移除窗口外元素：队列头部索引必须≥
输出结果：
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。
综合分析
时间复杂度：O(n)
- 每个元素入队和出队一次，总操作次数为O(n)，适合处理1e5数据。
空间复杂度：O(n)
dp数组存储每个格子的得分，队列最多存储k个元素。
优势：
- 单调队列优化：高效维护窗口最大值，避免重复计算。
- 逻辑清晰：代码简洁，适合处理大规模数据。
适用场景：
- 需要高效处理滑动窗口最大值的动态规划问题。
- 适用于实时系统或高频数据处理场景。
C语言
问题分析
我们需要找到从起点跳到终点的最大得分，每次跳跃步长不超过k。动态规划结合单调队列优化可以高效解决该问题。
解题思路
- 动态规划定义：
dp[i]表示跳到第i个格子时的最大得分。 - 状态转移：
dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。 - 单调队列优化：用双端队列维护窗口大小为k的区间，队列头部保持最大值，时间复杂度优化到O(n)。
代码实现
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data; // 存储索引的数组
int front; // 队列头部指针
int rear; // 队列尾部指针
int capacity; // 队列容量
} Deque;
// 创建双端队列
Deque* createDeque(int capacity) {
Deque *dq = (Deque*)malloc(sizeof(Deque));
dq->data = (int*)malloc(capacity * sizeof(int));
dq->front = 0;
dq->rear = -1;
dq->capacity = capacity;
return dq;
}
// 判断队列是否为空
int isEmpty(Deque *dq) {
return dq->front > dq->rear;
}
// 获取队首元素
int front(Deque *dq) {
return dq->data[dq->front];
}
// 弹出队首元素
void popFront(Deque *dq) {
if (!isEmpty(dq)) dq->front++;
}
// 获取队尾元素
int back(Deque *dq) {
return dq->data[dq->rear];
}
// 弹出队尾元素
void popBack(Deque *dq) {
if (!isEmpty(dq)) dq->rear--;
}
// 元素入队尾
void pushBack(Deque *dq, int val) {
dq->data[++dq->rear] = val;
}
int main() {
int n;
scanf("%d", &n);
int *score = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &score[i]);
}
int k;
scanf("%d", &k);
long long *dp = (long long*)malloc(n * sizeof(long long));
dp[0] = score[0]; // 初始化起点得分
Deque *dq = createDeque(n); // 创建容量为n的队列
pushBack(dq, 0); // 初始存入起点索引
for (int i = 1; i < n; i++) {
// 1. 移除超出窗口的元素（窗口左边界为i - k）
while (!isEmpty(dq) && front(dq) < i - k) {
popFront(dq);
}
// 2. 计算当前格子的最大得分
dp[i] = dp[front(dq)] + score[i];
// 3. 维护队列单调递减：移除队尾所有小于当前值的元素
while (!isEmpty(dq) && dp[i] >= dp[back(dq)]) {
popBack(dq);
}
pushBack(dq, i); // 当前索引入队
}
printf("%lld\n", dp[n - 1]);
// 释放内存
free(dq->data);
free(dq);
free(score);
free(dp);
return 0;
}
代码详细解析
输入处理：
scanf读取输入数据，包括格子数量n、分数数组score和最大跳跃步长k。
动态规划数组：
dp数组存储每个格子的最大得分，初始时dp[0] = score[0]。
双端队列初始化：
- 创建容量为
n的队列，初始存入起点索引0。
- 创建容量为
遍历每个格子：
- 移除窗口外元素：队列头部索引必须 ≥
i - k，否则弹出。 - 计算当前得分：队列头部对应窗口最大值，加上当前分数。
- 维护队列单调性：弹出队尾所有小于当前得分的元素。
- 索引入队：将当前索引加入队列尾部。
- 移除窗口外元素：队列头部索引必须 ≥
输出结果：
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。
综合分析
时间复杂度：O(n)
- 每个元素入队和出队一次，总操作次数为O(n)，适合处理1e5数据。
空间复杂度：O(n)
dp数组存储每个格子的得分，队列最多存储k个元素。
优势：
- 单调队列优化：高效维护窗口最大值，避免重复计算。
- 逻辑清晰：代码简洁，适合处理大规模数据。
适用场景：
- 需要高效处理滑动窗口最大值的动态规划问题。
- 适用于实时系统或高频数据处理场景。
GO
问题分析
我们需要找到从起点跳到终点的最大得分，每次跳跃步长不超过 k。动态规划结合单调队列优化可以高效解决该问题。
解题思路
- 动态规划定义：
dp[i]表示跳到第i个格子时的最大得分。 - 状态转移：
dp[i] = max(dp[i-k], dp[i-k+1], ..., dp[i-1]) + score[i]。 - 单调队列优化：使用双端队列维护窗口大小为
k的区间，队列头部保持最大值，时间复杂度优化到O(n)。
代码实现
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
// 读取输入
scanner.Scan()
n, _ := strconv.Atoi(scanner.Text())
scanner.Scan()
scoreStrs := strings.Split(scanner.Text(), " ")
score := make([]int, n)
for i := 0; i < n; i++ {
score[i], _ = strconv.Atoi(scoreStrs[i])
}
scanner.Scan()
k, _ := strconv.Atoi(scanner.Text())
// 处理边界情况
if n == 0 {
fmt.Println(0)
return
}
// 初始化动态规划数组和双端队列
dp := make([]int, n)
dp[0] = score[0]
deque := []int{0} // 存储索引的队列，初始放入起点
for i := 1; i < n; i++ {
// 1. 移除超出窗口范围的队首元素（窗口左边界为i-k）
for len(deque) > 0 && deque[0] < i-k {
deque = deque[1:]
}
// 2. 计算当前格子的最大得分
dp[i] = dp[deque[0]] + score[i]
// 3. 维护队列单调递减：移除队尾所有小于当前值的元素
for len(deque) > 0 && dp[i] >= dp[deque[len(deque)-1]] {
deque = deque[:len(deque)-1]
}
// 4. 当前索引入队
deque = append(deque, i)
}
fmt.Println(dp[n-1])
}
代码详细解析
输入处理：
- 使用
bufio.Scanner逐行读取输入。 - 第一行读取格子数量
n，第二行分割字符串转换为分数数组score，第三行读取最大跳跃步长k。
- 使用
初始化变量：
dp数组：dp[i]表示跳到第i个格子的最大得分，初始化为dp[0] = score[0]。deque双端队列：用切片模拟队列，初始存入起点索引0。
遍历每个格子：
- 移除窗口外元素：队列头部索引必须 ≥
i - k，否则弹出。 - 计算当前得分：队列头部对应窗口最大值，加上当前分数。
- 维护队列单调性：弹出队尾所有小于当前得分的元素。
- 索引入队：将当前索引加入队列尾部。
- 移除窗口外元素：队列头部索引必须 ≥
输出结果：
dp[n-1]表示终点的最大得分。
示例测试
示例1输入：
6
1 -1 -6 7 -17 7
2
输出：
14
解析：
- 路径为
0 → 1 → 3 → 5，得分1 + (-1) + 7 + 7 = 14。
示例2输入：
3
3 1 5
2
输出：
9
解析：
- 路径为
0 → 1 → 2，得分3 + 1 + 5 = 9。
综合分析
时间复杂度：
O(n)- 每个元素入队和出队一次，总操作次数为
O(n)，适合处理n ≤ 1e5的数据。
- 每个元素入队和出队一次，总操作次数为
空间复杂度：
O(n)dp数组存储每个格子的得分，队列最多存储k个元素。
优势：
- 单调队列优化：直接维护窗口最大值，避免重复计算。
- 代码简洁：使用切片模拟双端队列，逻辑清晰。
适用场景：
- 需要高效处理滑动窗口最大值的动态规划问题。
- 适用于高频数据处理或大规模输入场景。
更多内容：
https://www.kdocs.cn/l/cvk0eoGYucWA
本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！