Kimi LeetCode 3530. 有向无环图中合法拓扑排序的最大利润 Python3实现
以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 Python3 实现。
思路概述
- `n ≤ 22`，使用状压 DP（Bitmask DP）。
- `need[i]`：节点 `i` 的所有直接前驱的位掩码。
- `dp[mask]`：已经选了 `mask` 中这些节点，能获得的最大利润。
- 转移时，已选节点数为 `popcount(mask)`，下一个位置为 `pos = bitCount + 1`。枚举所有不在 mask 中且所有前驱都已选的节点 `i`，更新 `dp[mask | (1<<i)]`。
- 最终答案为 `dp[(1<<n) - 1]`。
复杂度
- 时间：`O(2^n · n)`，由于 `n ≤ 22`，约为 `2200` 万级别。
- 空间：`O(2^n)`
完整代码
```python
class Solution:
def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) -> int:
max_mask = 1 << n
# need[i] = 节点 i 的所有前驱节点的位掩码
need = [0] * n
# dp[mask] = 已选 mask 中节点时的最大利润
dp = [-1] * max_mask
dp[0] = 0
# 构建前驱掩码
for u, v in edges:
need[v] |= 1 << u
for mask in range(max_mask):
if dp[mask] == -1:
continue
pos = mask.bit_count() + 1 # 下一个位置（1-based）
for i in range(n):
# i 不在 mask 中，且 i 的所有前驱都已在 mask 中
if (mask & (1 << i)) == 0 and (need[i] & mask) == need[i]:
next_mask = mask | (1 << i)
dp[next_mask] = max(dp[next_mask], dp[mask] + score[i] * pos)
return dp[max_mask - 1]
```
关键点说明
1. `need[i]` 的构建：`need[v] |= 1 << u` 表示节点 `u` 必须在 `v` 之前。转移条件 `(need[i] & mask) == need[i]` 等价于 `need[i]` 是 `mask` 的子集，即 `i` 的所有前驱都已处理。
2. 位置计算：`pos = mask.bit_count() + 1`，因为 `mask` 中已有 `bit_count()` 个节点，下一个节点自然排在第 `bit_count() + 1` 位。
3. DP 初始化：`dp[0] = 0`，其余为 `-1` 表示不可达。由于 `score[i] ≥ 1` 且 `pos ≥ 1`，利润恒为正，`-1` 作为不可达标记是安全的。
4. 枚举顺序：按 `mask` 从小到大枚举，保证每个状态只被前面的状态更新一次。