• 科学计算

本篇技术指南以力扣双周赛 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_{j=0}^{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] * (i+1)最大。根据排序不等式（两组数同序相乘之和 ≥ 乱序 ≥ 反序），把score从小到大排序后累加score[i] * (i+1)即为最优解。

这一特判同时解释了状态转移方程的正确性：没有约束时，贪心按利润从小到大排在前面的位置（乘数小）即可达到最优，而状压 DP 是这一结论在有依赖关系下的推广。

以仓库测试数据为例（d.txt）：n=3, 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 的实现。

Python3（@cache一行实现记忆化）

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)

Java（memo数组显式记忆化）

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; // 记忆化 } }

C++（lambda 自递归 + 引用记忆化）

class Solution { public: int maxProfit(int n, vector<vector<int>>& edges, vector<int>& score) { if (edges.empty()) { ranges::sort(score); int ans = 0; for (int i = 0; i < n; i++) { ans += score[i] * (i + 1); } return ans; } // 记录每个节点的先修课（直接前驱） vector<int> pre(n); for (auto& e : edges) { pre[e[1]] |= 1 << e[0]; } vector<int> 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, 1<<n) 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 s>>j&1 == 0 && s|p == s { res = max(res, dfs(s|1<<j)+score[j]*(i+1)) } } 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_{j=0}^{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 s>>j&1 == 0 && s|p == s { f[s] = max(f[s], f[s|1<<j]+score[j]*(i+1)) } } } 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 s>>j&1 == 0 && s|p == s { newS := s | 1<<j f[newS] = max(f[newS], fs+score[j]*(i+1)) } } } return f[u-1] }

位运算进阶：只枚举未学课程

在内层循环中，与其遍历全部n门课再逐个判断(s >> j & 1) == 0，不如先计算未学集合 = 全集 ^ S，再通过lb = cus & -cus提取最低位的 1（lowbit 技巧）逐位取出未学课程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], fs+score[j]*(i+1)) } } }

刷表法中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.go：maxProfit（记忆化搜索）、maxProfit2（倒序查表法，注释明确标注"超时"）、maxProfit3（刷表法 + lowbit 位运算剪枝），三者共用slices.Sort+bits.OnesCount的位运算基础设施；
• leetcode/biweekly/155/d/d.txt：官方样例测试数据，含两组用例——n=2, edges=[[0,1]], score=[2,3]期望输出 8；n=3, edges=[[0,1],[0,2]], score=[1,6,3]期望输出 25；
• leetcode/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 的通用方法论：

1. 找约束：把"合法顺序"（本题为拓扑序）翻译成集合上的包含关系（pre[j] ⊆ S），这是能否使用状压的关键一步；
2. 定状态：dfs(S)表示"已经完成 S 中元素"时的最优子问题，转移时枚举下一个加入的元素 j，收益项通常与|S|+1（当前序号）相关；
3. 选写法：自顶向下记忆化搜索最直观；需要常数优化时，优先把递归翻译成递推，并用刷表法跳过不可达状态；位运算（lowbit + TrailingZeros）枚举未选元素是通用加速手段。

这类题目在题单中归属于「排列型 ① 相邻无关」子类（同属动态规划专题），其余典型变体包括：带相邻约束的排列型（如旅行商问题）、带收益函数依赖当前序号的排列型、以及多集合互相约束的复合状压等，掌握本题的推演过程后均可举一反三。

• 科学计算