1. 题目背景与核心考察点解析最近在算法练习平台上频繁看到oj104、oj105、oj106这三道经典题目的讨论。作为算法进阶路上的必经关卡这三道题涵盖了动态规划、图论和数据结构等核心知识点。本文将结合我个人刷题经验深入剖析这三道题的解题思路和实现细节。oj104通常考察的是动态规划中的背包问题变种需要处理带有特殊限制条件的物品选择问题。oj105则偏向图论中的最短路径算法应用常涉及Dijkstra或Floyd算法的变形。而oj106往往与高级数据结构相关可能需要实现特殊的树结构或并查集优化。提示这三道题在各大公司的笔试中出现频率较高建议至少掌握两种不同解法2. oj104 动态规划解法详解2.1 问题重述与建模oj104的典型描述是给定一组物品每个物品有重量w[i]和价值v[i]在背包容量限制为W的情况下要求选择的物品总重量不超过W且满足某种特殊条件如某些物品必须选/不能同时选等求最大总价值。这类问题的关键在于识别出基础背包模型01背包/完全背包/多重背包正确处理附加的限制条件设计合适的状态转移方程2.2 状态定义与转移方程以最常见的01背包变种为例我们定义dp[i][j]表示考虑前i个物品当前背包重量为j时的最大价值。基础状态转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])当遇到必须选第k个物品的限制时需要预处理先强制选择该物品调整剩余容量然后在剩余物品上运行标准背包算法2.3 空间优化技巧通过滚动数组可以将空间复杂度从O(nW)优化到O(W)dp [0]*(W1) for i in range(n): for j in range(W, w[i]-1, -1): dp[j] max(dp[j], dp[j-w[i]] v[i])注意逆序遍历是为了防止同一物品被多次选择3. oj105 图论问题实战3.1 题目特征分析oj105通常给出一个带权有向图要求计算特定节点间的最短路径处理存在负权边的情况满足额外的访问限制条件3.2 Dijkstra算法的适用与限制标准Dijkstra算法实现import heapq def dijkstra(graph, start): distances {node: float(inf) for node in graph} distances[start] 0 heap [(0, start)] while heap: current_dist, current_node heapq.heappop(heap) if current_dist distances[current_node]: continue for neighbor, weight in graph[current_node].items(): distance current_dist weight if distance distances[neighbor]: distances[neighbor] distance heapq.heappush(heap, (distance, neighbor)) return distances当图中存在负权边时Dijkstra算法可能失效此时应改用SPFA或Bellman-Ford算法。3.3 处理特殊限制条件常见变种包括途径特定节点的最短路径分段计算A→C→B shortest(A,C) shortest(C,B)边权随时间变化需要将时间维度纳入状态定义限制路径边数使用分层图技术4. oj106 数据结构应用4.1 题目类型识别oj106通常涉及以下数据结构并查集带权或扩展域线段树/树状数组Trie树/后缀自动机平衡二叉搜索树4.2 并查集高级应用带权并查集实现示例class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0]*n self.weight [0]*n # 维护节点到父节点的权值 def find(self, x): if self.parent[x] ! x: orig_parent self.parent[x] self.parent[x] self.find(self.parent[x]) self.weight[x] self.weight[orig_parent] return self.parent[x] def union(self, x, y, w): x_root self.find(x) y_root self.find(y) if x_root y_root: return if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root self.weight[x_root] w - self.weight[x] self.weight[y] else: self.parent[y_root] x_root self.weight[y_root] -w - self.weight[y] self.weight[x] if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 14.3 线段树优化技巧动态开点线段树实现区间查询class Node: __slots__ [l,r,left,right,val] def __init__(self, l, r): self.l l self.r r self.left None self.right None self.val 0 class SegmentTree: def __init__(self, l, r): self.root Node(l, r) def update(self, node, idx, val): if node.l node.r: node.val val return mid (node.l node.r) // 2 if idx mid: if not node.left: node.left Node(node.l, mid) self.update(node.left, idx, val) else: if not node.right: node.right Node(mid1, node.r) self.update(node.right, idx, val) node.val (node.left.val if node.left else 0) \ (node.right.val if node.right else 0) def query(self, node, l, r): if not node or node.r l or node.l r: return 0 if l node.l and node.r r: return node.val return self.query(node.left, l, r) self.query(node.right, l, r)5. 常见错误与调试技巧5.1 oj104典型错误初始化不正确忘记将dp[0][0]初始化为0错误地将所有位置初始化为-INF边界条件处理不当没有检查j-w[i]是否越界特殊限制条件判断顺序错误调试建议打印中间状态矩阵用小规模测试用例手动验证5.2 oj105易错点优先队列实现错误忘记处理重复节点距离更新条件不完整负权环检测遗漏Bellman-Ford算法中迭代次数不足没有正确判断松弛操作是否还能继续调试技巧可视化图的邻接表表示检查每个节点的入队/出队次数5.3 oj106常见问题并查集路径压缩错误忘记维护权值关系压缩时父节点更新顺序错误线段树更新延迟懒标记下传不及时区间划分边界条件错误调试方法为每个操作添加日志输出验证小规模输入的中间结果6. 性能优化策略6.1 oj104优化方向二进制拆分优化多重背包将物品数量拆分为1,2,4,...的幂次组合转化为01背包问题求解单调队列优化维护一个滑动窗口最值将时间复杂度从O(nW)降到O(n)6.2 oj105加速技巧双向Dijkstra从起点和终点同时开始搜索当两边的优先队列相遇时终止A*启发式搜索设计合理的启发函数h(x)优先扩展最有希望的节点6.3 oj106高效实现并查集路径压缩优化def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x]线段树懒标记优化将区间更新延迟到实际查询时执行减少不必要的节点更新操作在实际刷题过程中建议先写出基础解法再逐步引入优化。我个人的经验是先确保正确性再考虑优化往往能避免很多难以发现的边界条件错误。对于这三道题至少要练习到能在30分钟内完成编码和基本测试的程度这样才能在笔试或面试中游刃有余。