东华大学计算机考研复试OJ刷题指南：动态规划与图论实战

1. 项目背景与核心价值

作为一名经历过东华大学计算机考研复试的过来人，我深知OJ（Online Judge）刷题在复试环节的重要性。去年备考期间，我坚持了60天的"每日3题"打卡计划，最终在机试环节取得了前5%的成绩。这个系列文章就是将我当时的刷题笔记进行系统整理，重点挑选了具有代表性的题目集群（第43-45天）进行深度复盘。

东华复试机试常考知识点集中在动态规划、图论和字符串处理三大板块，而43-45天的题目组合恰好覆盖了这三个方向的典型题型。不同于普通题解，这个复盘系列会特别注重：

• 同类题目的解题模式提炼
• 实际编码中的边界条件处理
• 考场环境下的时间分配策略

2. 题目43：矩阵链乘法优化（动态规划典型题）

2.1 问题重述

给定n个矩阵的维度序列p（其中第i个矩阵维度为p[i-1]×p[i]），计算最优的矩阵相乘顺序，使得标量乘法运算次数最少。

输入示例：

[30,35,15,5,10,20,25]

表示有5个矩阵：A1(30×35)、A2(35×15)...A5(10×20)

2.2 核心解法剖析

动态规划解法需要构建两个关键表格：

1. m[i][j]：计算Ai...Aj的最小乘法次数
2. s[i][j]：记录最优分割点k

递推公式：

for l in range(2, n+1): # 链长度 for i in range(0, n-l+1): j = i + l - 1 m[i][j] = float('inf') for k in range(i, j): cost = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1] if cost < m[i][j]: m[i][j] = cost s[i][j] = k

2.3 考场实战技巧

1. 维度处理技巧：题目给出的p数组长度是n+1（n个矩阵）
2. 初始化陷阱：当i==j时m[i][j]=0（单个矩阵无需计算）
3. 常见WA原因：
   • 错误地将p[0]和p[1]当作第一个矩阵的维度
   • 没有处理链长度为1的边界情况

注意：东华OJ对输出格式要求严格，需要按照指定格式输出最优分割方案，建议提前准备好括号输出模板。

3. 题目44：地铁换乘规划（图论应用）

3.1 问题场景

给定城市地铁线路图（邻接表形式），计算从起点站到终点站的最少换乘次数。不同于常规最短路径，本题的权重是换乘次数而非距离。

输入示例：

Line1: A B C D E Line2: C F G H Line3: E H I

查询：A → I

3.2 分层图建模技巧

常规的Dijkstra算法无法直接适用，需要特殊处理：

1. 构建线路-车站二分图
2. 同一线路上的车站两两建立边（权重0）
3. 同一车站在不同线路间建立换乘边（权重1）

# 建图伪代码 graph = defaultdict(dict) for line in lines: stations = line.split() for s in stations: for t in stations: if s != t: graph[s][t] = 0 # 同线路免费通行 # 添加换乘边 for station in transfer_stations: for line1 in station_lines[station]: for line2 in station_lines[station]: if line1 != line2: graph[line1][line2] = 1

3.3 实战优化策略

1. 双向BFS适用性：由于换乘次数通常<5，双向搜索效率更高
2. 预处理技巧：提前计算各线路的换乘站索引
3. 输入处理陷阱：注意站名可能包含空格（实际考场出现过）

4. 题目45：DNA序列对齐（字符串DP）

4.1 生物信息学背景

给定两条DNA序列s1和s2，允许进行以下操作：

• 插入空格（代价a）
• 删除字符（代价b）
• 替换字符（代价c if不同，0 if相同） 求最小编辑距离。

特殊要求：需要输出具体操作序列

4.2 动态规划实现

构建dp表的同时需要记录操作路径：

dp = [[0]*(n+1) for _ in range(m+1)] path = [[None]*(n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): cases = [ (dp[i-1][j-1] + (0 if s1[i-1]==s2[j-1] else c), 'replace'), (dp[i-1][j] + b, 'delete'), (dp[i][j-1] + a, 'insert') ] min_val, op = min(cases, key=lambda x: x[0]) dp[i][j] = min_val path[i][j] = op

4.3 操作序列回溯技巧

def traceback(i, j): if i == 0 and j == 0: return [] if path[i][j] == 'replace': return traceback(i-1,j-1) + [f'replace {s1[i-1]}→{s2[j-1]}'] elif path[i][j] == 'delete': return traceback(i-1,j) + [f'delete {s1[i-1]}'] else: return traceback(i,j-1) + [f'insert {s2[j-1]}']

关键细节：东华OJ对操作序列的输出顺序有严格要求，必须是正向操作序列而非逆向。

5. 三日题目共性分析

5.1 动态规划的统一思维

这三题虽然领域不同，但都体现了DP的核心思想：

1. 最优子结构：问题的最优解包含子问题的最优解
2. 状态定义：用dp[i][j]表示子问题的解
3. 状态转移：建立递推关系式

5.2 东华OJ的出题特点

通过分析近年真题，发现以下规律：

1. 输入格式陷阱：故意设计非常规输入方式（如带空格的站名）
2. 输出严格校验：要求操作序列的格式必须完全匹配
3. 时间限制宽松：更注重正确性而非极端优化

5.3 三日刷题时间分配建议

6. 高频错误与调试技巧

6.1 动态规划常见bug

1. 初始化错误：特别是边界条件处理
2. 索引偏移：题目输入从0开始还是1开始
3. 状态转移遗漏：未考虑所有可能情况

调试建议：

# 打印dp表辅助调试 for row in dp: print(' '.join(f'{x:3d}' for x in row))

6.2 图论问题易错点

1. 建图时边权重设置错误
2. 未处理重边情况
3. 优先队列未更新距离

6.3 字符串处理陷阱

1. 特殊字符处理（如换行符）
2. 空字符串边界情况
3. Unicode与ASCII混淆

7. 扩展训练建议

针对这组题目，推荐以下进阶练习：

1. 矩阵链乘法→最优二叉搜索树
2. 地铁换乘→带权重的多模式路径规划
3. DNA对齐→带affine gap penalty的序列对齐

我个人在复试准备后期，会刻意训练"三题连刷"的模式：用2小时连续完成三道不同知识点的题目，模拟真实考场环境。实测发现这种训练能显著提高思维切换能力和时间掌控水平。