科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以力扣双周赛 155 第 4 题「DAG 中合法拓扑序的最大利润」Maximum Profit From Valid Topological Order in DAG为实战载体完整讲解排列型状压 DP 的三种标准写法记忆化搜索、倒序递推查表法与正序刷表法并给出位运算优化技巧与无边特判下的排序不等式快速解法。读者学完后能够独立推导这类带约束的排列顺序优化问题的状态定义、转移方程与复杂度分析并将同一套路迁移到其他排列型状压题目中。文章同时给出该题在当前仓库codeforces-go 算法竞赛模板库中的 Go 实现与测试用例作为可验证的工程佐证。一、题目核心思路把拓扑序理解为先修课关系本题输入三个参数课程数量n、有向边集合edges表示课程之间的先后依赖关系与每个课程的利润系数score。我们需要求一个合法拓扑序使得按该顺序依次学完所有课程时总利润最大其中第k个从 1 开始计数学习的课程贡献score[j] * k。关键思路把拓扑序理解为先修课关系——在学习课程j之前j的所有先修课直接前驱必须全部学完。这一点把拓扑序这一图论概念彻底转化成了集合逐步扩张的过程从而可以套用排列型状压 DP 的标准框架。若读者尚未接触过状压 DP建议先完成 526. 优美的排列经典排列型状压入门题再做本题效果更好。二、状态定义与状态转移方程定义dfs(S)表示在已学课程集合为S的情况下学完剩余未学课程可以获得的最大利润。考虑下一门课程学哪个枚举下一门要学习的课程为j 0, 1, 2, ..., n-1要求满足j ∉ S且pre[j] ⊆ S其中pre[j]表示j的先修课集合。选择j之后问题变成在已学课程集合为S ∪ {j}的情况下学完剩余未学课程可以获得的最大利润即dfs(S ∪ {j})。取最大值得到状态转移方程dfs(S) max_{j0}^{n-1} dfs(S ∪ {j}) score[j] * (|S| 1)其中j ∉ S且pre[j] ⊆ S|S|表示集合S的大小。当前课程是第|S|1个学习的因此本次收益为score[j] * (|S|1)。递归边界dfs(U) 0其中全集U {0, 1, 2, ..., n-1}。递归到S U的状态表示所有课程全部学完没有剩余未学课程可以获得的最大利润为0。递归入口dfs(∅)也就是答案。∅表示空集因为一开始什么课程也没有学。集合操作在代码层面一律用二进制位运算实现整数第j位为 1 表示课程j已学1 j表示把课程j加入集合(s j 1) 0判断课程j未学(s | p) s判断先修课集合p是否全部包含于s。这套从集合论到位运算的编码方式是所有状压 DP 的通用基础。三、特判优化无边时利用排序不等式 O(n log n) 秒解如果edges是空的没有任何依赖关系问题退化为给score任意排一个顺序使Σ score[i] * (i1)最大。根据排序不等式两组数同序相乘之和 ≥ 乱序 ≥ 反序把score从小到大排序后累加score[i] * (i1)即为最优解。这一特判同时解释了状态转移方程的正确性没有约束时贪心按利润从小到大排在前面的位置乘数小即可达到最优而状压 DP 是这一结论在有依赖关系下的推广。以仓库测试数据为例d.txtn3, edges[[0,1],[0,2]], score[1,6,3]存在依赖时答案25说明先学课程 0利润 1×1再按利润从小到大学 3 和 6贡献 3×2 6×3 24总计 25——贪心思想在有向边约束下仍以小利润乘小序号为局部最优方向但必须服从先修课约束。四、写法一记忆化搜索自顶向下记忆化搜索是最直观的写法直接翻译递归定义用缓存数组/装饰器避免重复计算。以下分别给出 Python、Java、C 与 Go 的实现。Python3cache一行实现记忆化class Solution: def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) - int: if not edges: score.sort() return sum(s * i for i, s in enumerate(score, 1)) # 记录每个节点的先修课直接前驱 pre [0] * n for x, y in edges: pre[y] | 1 x cache # 缓存装饰器避免重复计算 dfs一行代码实现记忆化 def dfs(s: int) - int: res 0 i s.bit_count() 1 # 已学课程数加一 # 枚举还没学过的课程 j且 j 的所有先修课都学完了 for j, p in enumerate(pre): if (s j 1) 0 and (s | p) s: r dfs(s | 1 j) score[j] * i if r res: # 手写 max res r return res return dfs(0)Javamemo数组显式记忆化class Solution { public int maxProfit(int n, int[][] edges, int[] score) { if (edges.length 0) { Arrays.sort(score); int ans 0; for (int i 0; i n; i) { ans score[i] * (i 1); } return ans; } // 记录每个节点的先修课直接前驱 int[] pre new int[n]; for (int[] e : edges) { pre[e[1]] | 1 e[0]; } int[] memo new int[1 n]; return dfs(0, pre, score, memo); } private int dfs(int s, int[] pre, int[] score, int[] memo) { if (memo[s] 0) { // 之前计算过 return memo[s]; } int res 0; int i Integer.bitCount(s); // 已学课程数 // 枚举还没学过的课程 j且 j 的所有先修课都学完了 for (int j 0; j pre.length; j) { if ((s j 1) 0 (s | pre[j]) s) { res Math.max(res, dfs(s | 1 j, pre, score, memo) score[j] * (i 1)); } } return memo[s] res; // 记忆化 } }Clambda 自递归 引用记忆化class Solution { public: int maxProfit(int n, vectorvectorint edges, vectorint score) { if (edges.empty()) { ranges::sort(score); int ans 0; for (int i 0; i n; i) { ans score[i] * (i 1); } return ans; } // 记录每个节点的先修课直接前驱 vectorint pre(n); for (auto e : edges) { pre[e[1]] | 1 e[0]; } vectorint memo(1 n); auto dfs - int { int res memo[s]; // 注意这里是引用 if (res) { // 之前计算过 return res; } int i popcount((uint32_t) s); // 已学课程数 // 枚举还没学过的课程 j且 j 的所有先修课都学完了 for (int j 0; j n; j) { if ((s j 1) 0 (s | pre[j]) s) { res max(res, dfs(s | 1 j) score[j] * (i 1)); } } return res; }; return dfs(0); } };Go闭包递归 命名返回值 defer 记忆化func maxProfit(n int, edges [][]int, score []int) int { if len(edges) 0 { slices.Sort(score) for i, s : range score { ans s * (i 1) } return } // 记录每个节点的先修课直接前驱 pre : make([]int, n) for _, e : range edges { pre[e[1]] | 1 e[0] } memo : make([]int, 1n) var dfs func(s int) int dfs func(s int) (res int) { m : memo[s] if *m 0 { // 之前计算过 return *m } defer func() { *m res }() // 记忆化 i : bits.OnesCount(uint(s)) // 已学课程数 // 枚举还没学过的课程 j且 j 的所有先修课都学完了 for j, p : range pre { if sj1 0 s|p s { res max(res, dfs(s|1j)score[j]*(i1)) } } return } return dfs(0) }实现要点pre[y] | 1 x把每条边(x, y)的起点x写入y的先修课位图O(m) 完成依赖预处理用(s | p) s判断pre[j] ⊆ S比逐位检查更简洁记忆化数组大小为1 n恰好覆盖全部2^n个集合状态。五、写法二1:1 翻译成递推查表法倒序记忆化搜索的递部分可以去掉只保留归部分即自底向上计算。f[S]的定义与dfs(S)完全一致在已学课程集合为S的情况下学完剩余未学课程可以获得的最大利润。状态转移方程同样为f[S] max_{j0}^{n-1} f[S ∪ {j}] score[j] * (|S| 1)初始值f[U] 0翻译自递归边界dfs(U) 0答案为f[∅]翻译自递归入口dfs(∅)。由于f[S]依赖更大的集合f[S ∪ {j}]倒序枚举S从2^n - 2递减到0即可保证依赖项已计算。下面给出 Python 与 Go 版本⚠ 注意这个写法在本题可能超时详见写法三# 超时了请看写法三 class Solution: def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) - int: if not edges: score.sort() return sum(s * i for i, s in enumerate(score, 1)) # 记录每个节点的先修课直接前驱 pre [0] * n for x, y in edges: pre[y] | 1 x f [0] * (1 n) for s in range((1 n) - 2, -1, -1): res 0 i s.bit_count() 1 # 已学课程数加一 # 枚举还没学过的课程 j且 j 的所有先修课都学完了 for j, p in enumerate(pre): if (s j 1) 0 and (s | p) s: r f[s | 1 j] score[j] * i if r res: # 手写 max res r f[s] res return f[0]// 超时了请看写法三 func maxProfit2(n int, edges [][]int, score []int) (ans int) { if len(edges) 0 { slices.Sort(score) for i, s : range score { ans s * (i 1) } return } // 记录每个节点的先修课直接前驱 pre : make([]int, n) for _, e : range edges { pre[e[1]] | 1 e[0] } u : 1 n f : make([]int, u) for s : u - 2; s 0; s-- { i : bits.OnesCount(uint(s)) // 已学课程数 // 枚举还没学过的课程 j且 j 的所有先修课都学完了 for j, p : range pre { if sj1 0 s|p s { f[s] max(f[s], f[s|1j]score[j]*(i1)) } } } return f[0] }查表法的问题在于它要枚举全部2^n个状态即使某些状态在拓扑序上根本不可达例如先学了后置课程、前驱却还没学也要执行完整的内层循环浪费大量计算。六、写法三刷表法正序 位运算剪枝在动态规划中用转移来源更新当前状态叫查表法写法二用当前状态去更新其他状态叫刷表法写法三。刷表法顺向扩展从合法状态S出发枚举可加入的课程j更新f[S ∪ {j}]。这样做的好处是——如果一个状态从未被更新过说明这个状态不合法比如已经学完后面的课程但前面的课程还没学无需执行内层循环。在依赖较多的图上可达状态远少于2^n因此刷表法能显著减少无效计算解决写法二的超时问题。Python 实现class Solution: def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) - int: if not edges: score.sort() return sum(s * i for i, s in enumerate(score, 1)) # 记录每个节点的先修课直接前驱 pre [0] * n for x, y in edges: pre[y] | 1 x f [-1] * (1 n) f[0] 0 for s, fs in enumerate(f): if fs 0: # 不合法状态比如已经学完后面的课程但前面的课程还没学 continue i s.bit_count() 1 # 已学课程数加一 # 枚举还没学过的课程 j且 j 的所有先修课都学完了 for j, p in enumerate(pre): if (s j 1) 0 and (s | p) s: new_s s | 1 j r f[s] score[j] * i if r f[new_s]: # 手写 max f[new_s] r return f[-1]Go 实现含-1哨兵标记非法状态func maxProfit3(n int, edges [][]int, score []int) (ans int) { if len(edges) 0 { slices.Sort(score) for i, s : range score { ans s * (i 1) } return } // 记录每个节点的先修课直接前驱 pre : make([]int, n) for _, e : range edges { pre[e[1]] | 1 e[0] } u : 1 n f : make([]int, u) for s : 1; s u; s { f[s] -1 } for s, fs : range f { if fs 0 { // 不合法状态比如已经学完后面的课程但前面的课程还没学 continue } i : bits.OnesCount(uint(s)) // 已学课程数 // 枚举还没学过的课程 j且 j 的所有先修课都学完了 for j, p : range pre { if sj1 0 s|p s { newS : s | 1j f[newS] max(f[newS], fsscore[j]*(i1)) } } } return f[u-1] }位运算进阶只枚举未学课程在内层循环中与其遍历全部n门课再逐个判断(s j 1) 0不如先计算未学集合 全集 ^ S再通过lb cus -cus提取最低位的 1lowbit 技巧逐位取出未学课程j用bits.TrailingZeros得到其编号。这样循环次数与尚未学习的课程数成正比进一步压缩常数for s, fs : range f { if fs 0 { // 不合法状态 continue } i : bits.OnesCount(uint(s)) // 已学课程数 // 只枚举还没学过的课程cus 是未学课程集合 for cus, lb : u-1^s, 0; cus 0; cus ^ lb { lb cus -cus j : bits.TrailingZeros(uint(lb)) if s|pre[j] s { // 先修课已全部学完 newS : s | lb f[newS] max(f[newS], fsscore[j]*(i1)) } } }刷表法中f[0] 0是唯一启动点所有合法的拓扑序状态从它逐层扩张而来最终f[U]即为答案任何违反先修课约束的状态由于永远无法被更新始终保持-1被continue跳过。七、复杂度分析三种写法的复杂度结论一致时间复杂度O(m n·2^n)其中 m 是edges的长度。由于每个状态只会计算一次DP 时间复杂度 状态个数 × 单个状态计算时间状态个数为 O(2^n)单个状态计算时间为 O(n)故为 O(n·2^n)另有 O(m) 的先修课预处理。无边的特判分支为 O(n log n)排序。空间复杂度O(2^n)保存多少状态就需要多少空间记忆化数组/DP 数组。在实际数据范围n 通常 ≤ 12~15下2^n 状态完全可行刷表法在依赖约束严格时实际遍历的状态数会明显少于 2^n从而将常数进一步压低。八、仓库中的实现与测试验证当前仓库完整收录了本题三种写法的 Go 实现与上文代码一一对应leetcode/biweekly/155/d/d.gomaxProfit记忆化搜索、maxProfit2倒序查表法注释明确标注超时、maxProfit3刷表法 lowbit 位运算剪枝三者共用slices.Sortbits.OnesCount的位运算基础设施leetcode/biweekly/155/d/d.txt官方样例测试数据含两组用例——n2, edges[[0,1]], score[2,3]期望输出 8n3, edges[[0,1],[0,2]], score[1,6,3]期望输出 25leetcode/biweekly/155/d/d_test.go通过testutil.RunLeetCodeFuncWithFile(t, maxProfit, d.txt, 0)驱动样例回归测试测试数据解析逻辑位于 leetcode/testutil/leetcode.go按行解析参数与期望输出支持嵌套数组语法该测试文件头部注明由 copypasta/template/leetcode/generator.go 的代码生成器自动生成——仓库以题解 可运行测试的方式沉淀每场周赛的解法。在仓库根目录执行go test ./leetcode/biweekly/155/d/即可本地运行该用例验证三种写法的输出与样例一致超时写法在测试数据规模下依然能得出正确结果。九、套路总结排列型状压 DP 三步走回顾本题可以提炼出排列型状压 DP 的通用方法论找约束把合法顺序本题为拓扑序翻译成集合上的包含关系pre[j] ⊆ S这是能否使用状压的关键一步定状态dfs(S)表示已经完成 S 中元素时的最优子问题转移时枚举下一个加入的元素 j收益项通常与|S|1当前序号相关选写法自顶向下记忆化搜索最直观需要常数优化时优先把递归翻译成递推并用刷表法跳过不可达状态位运算lowbit TrailingZeros枚举未选元素是通用加速手段。这类题目在题单中归属于「排列型 ① 相邻无关」子类同属动态规划专题其余典型变体包括带相邻约束的排列型如旅行商问题、带收益函数依赖当前序号的排列型、以及多集合互相约束的复合状压等掌握本题的推演过程后均可举一反三。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode 329 矩阵中的最长递增路径从暴力 DFS 到记忆化 DP 与 Kahn 拓扑排序的完整解法LeetCode 329 矩阵中的最长递增路径从暴力 DFS 到记忆化 DP 与 Kahn 拓扑排序的完整解法 导读 本文以 articles/longest示例工程教程LeetCode 2050 Parallel Courses III 详解DAG 加权最长路径与 DFS 记忆化、迭代 DFS、Kahn 拓扑排序三解法LeetCode 2050 Parallel Courses III 详解DAG 加权最长路径与 DFS 记忆化、迭代 DFS、Kahn 拓扑排序三解法 本篇示例工程教程Get-Shit-Done 小数阶段Decimal Phase计算与紧急插入实战指南Get Shit Done 小数阶段Decimal Phase计算与紧急插入实战指南 在 Get Shit DoneGSD基于编号的阶段式开发流程中当示例工程教程上一篇baoyu-diagram 技能实战指南用单一自包含 SVG 生成专业深色系技术图表下一篇内存故障深度诊断与系统稳定性保障Memtest86专业应用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考