复旦计算机考研机试：动态规划与图论实战指南

1. 项目背景与学习目标最近在准备计算机考研复试的过程中我发现复旦大学的408机试环节特别注重考察算法与数据结构的实际应用能力。作为过来人我想记录下自己备战复旦机试的第四天学习历程希望能给同样在准备复试的同学们一些参考。第四天的学习重点主要集中在动态规划和图论这两个高频考点上。复旦机试的题目往往不会直接考察课本上的基础算法而是会将这些算法融入实际应用场景中进行考察。因此在复习时不能只停留在理解算法原理的层面更要注重算法在实际问题中的应用能力。2. 动态规划专题精讲2.1 动态规划核心思想动态规划是复旦机试中的必考内容几乎每年都会出现1-2道相关题目。在复习时我特别注重理解动态规划的三个核心要素最优子结构问题的最优解包含子问题的最优解重叠子问题递归算法会重复计算相同的子问题状态转移方程定义如何从一个状态转移到另一个状态以经典的背包问题为例我重新推导了状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])其中dp[i][j]表示前i个物品放入容量为j的背包的最大价值。2.2 动态规划解题模板通过分析历年真题我总结出一个适用于大多数动态规划题目的解题模板定义dp数组的含义确定初始条件推导状态转移方程确定遍历顺序举例验证dp数组在练习时我特别注重第5步的验证过程。很多同学在考试时容易忽略这一步导致写出的代码虽然看起来正确但实际上存在逻辑错误。2.3 动态规划优化技巧复旦机试对算法的时间复杂度要求很高因此必须掌握动态规划的空间优化技巧。常见的优化方法包括滚动数组将二维dp数组优化为一维状态压缩使用位运算等技巧减少状态表示单调队列优化适用于特定类型的状态转移方程我重点练习了将二维dp数组优化为一维的技巧。以背包问题为例优化后的状态转移方程为dp[j] max(dp[j], dp[j-w[i]] v[i])需要注意的是这种情况下遍历顺序需要从后往前以避免重复计算。3. 图论算法实战3.1 图的表示方法复旦机试中的图论题目通常不会给出图的显式表示而是需要考生根据题目描述自行构建图模型。常见的图的表示方法包括邻接矩阵适合稠密图邻接表适合稀疏图边列表适合某些特定算法我练习了使用vector实现的邻接表表示法vectorvectorint adj(n); for(int i0; im; i){ int u, v; cin u v; adj[u].push_back(v); adj[v].push_back(u); // 无向图需要双向添加 }3.2 最短路径算法Dijkstra算法是复旦机试中的高频考点。在复习时我特别注意以下几点优先队列的实现方式如何处理负权边不能使用Dijkstra路径记录的实现方法我实现了一个带路径记录的Dijkstra算法vectorint dist(n, INF); vectorint pre(n, -1); priority_queuepairint,int pq; dist[start] 0; pq.push({0, start}); while(!pq.empty()){ auto [d, u] pq.top(); pq.pop(); if(-d dist[u]) continue; for(auto [v, w] : adj[u]){ if(dist[v] dist[u] w){ dist[v] dist[u] w; pre[v] u; pq.push({-dist[v], v}); } } }3.3 最小生成树算法Kruskal和Prim算法都需要熟练掌握。我重点练习了Kruskal算法的实现特别是并查集的使用vectorint parent(n); iota(parent.begin(), parent.end(), 0); functionint(int) find [](int x){ return parent[x] x ? x : parent[x] find(parent[x]); }; sort(edges.begin(), edges.end()); int res 0; for(auto [w, u, v] : edges){ u find(u); v find(v); if(u ! v){ res w; parent[u] v; } }4. 真题实战演练4.1 动态规划真题解析我选择了一道复旦往年的动态规划真题进行练习题目描述给定一个正整数数组找出其中不相邻元素组成的子序列的最大和。这道题是典型的动态规划问题。我按照之前总结的解题模板定义dp[i]为前i个元素中不相邻子序列的最大和初始条件dp[0]nums[0], dp[1]max(nums[0],nums[1])状态转移方程dp[i] max(dp[i-1], dp[i-2]nums[i])最终结果为dp[n-1]实现代码如下int rob(vectorint nums) { int n nums.size(); if(n 1) return nums[0]; vectorint dp(n); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for(int i2; in; i){ dp[i] max(dp[i-1], dp[i-2]nums[i]); } return dp[n-1]; }4.2 图论真题解析另一道图论真题是题目描述给定一个n个节点的有向图判断是否存在从节点0到节点n-1的路径。这道题可以使用BFS或DFS解决。我选择用BFS实现bool canReach(vectorvectorint graph) { int n graph.size(); queueint q; vectorbool visited(n, false); q.push(0); visited[0] true; while(!q.empty()){ int u q.front(); q.pop(); if(u n-1) return true; for(int v : graph[u]){ if(!visited[v]){ visited[v] true; q.push(v); } } } return false; }5. 常见错误与调试技巧5.1 动态规划常见错误在练习过程中我总结了几种常见的动态规划错误初始条件设置不当特别是边界情况的处理状态转移方程错误没有考虑所有可能的情况遍历顺序错误特别是空间优化后的遍历顺序数组越界没有正确处理索引范围调试技巧打印dp数组的中间结果使用小规模测试用例手动验证特别注意边界条件n0,1等5.2 图论常见错误图论算法中容易出现的错误包括图的表示错误有向图/无向图混淆访问标记遗漏导致无限循环优先队列的比较函数错误并查集的路径压缩或按秩合并实现错误调试技巧可视化小规模图的遍历过程检查每个节点的邻接表是否正确使用断言验证不变量6. 学习心得与时间规划经过第四天的学习我对动态规划和图论的理解更加深入了。最大的收获是建立了系统的解题思路而不是单纯地记忆算法模板。在时间规划方面我采用专题突破真题演练的模式上午专题知识梳理与模板代码实现下午真题练习与错题分析晚上复习巩固与知识拓展对于准备复旦机试的同学我的建议是重视基础算法的深入理解多做真题熟悉出题风格注重代码实现的细节和效率建立错题本定期复习易错点