Kimi LeetCode 3530. 有向无环图中合法拓扑排序的最大利润 Java实现

以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 Java 实现。

思路概述

- `n ≤ 22`，使用状压 DP（Bitmask DP）。
- `need[i]`：节点 `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)`

完整代码

```java
class Solution {
public int maxProfit(int n, int[][] edges, int[] score) {
final int maxMask = 1 << n;

// need[i] = 节点 i 的所有前驱节点的位掩码
int[] need = new int[n];

// dp[mask] = 已选 mask 中节点时的最大利润
int[] dp = new int[maxMask];
Arrays.fill(dp, -1);
dp[0] = 0;

// 构建前驱掩码
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
need[v] |= 1 << u;
}

for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] == -1) continue;

int pos = Integer.bitCount(mask) + 1; // 下一个位置（1-based）

for (int i = 0; i < n; i++) {
// i 不在 mask 中，且 i 的所有前驱都已在 mask 中
if ((mask & (1 << i)) == 0 && (need[i] & mask) == need[i]) {
int nextMask = mask | (1 << i);
dp[nextMask] = Math.max(dp[nextMask], dp[mask] + score[i] * pos);
}
}
}

return dp[maxMask - 1];
}
}
```

关键点说明

1. `need[i]` 的构建：`need[v] |= 1 << u` 表示节点 `u` 必须在 `v` 之前。转移条件 `(need[i] & mask) == need[i]` 等价于 `need[i]` 是 `mask` 的子集，即 `i` 的所有前驱都已处理。
2. 位置计算：`pos = bitCount(mask) + 1`，因为 `mask` 中已有 `bitCount(mask)` 个节点，下一个节点自然排在第 `bitCount + 1` 位。
3. DP 初始化：`dp[0] = 0`，其余为 `-1` 表示不可达。由于 `score[i] ≥ 1` 且 `pos ≥ 1`，利润恒为正，`-1` 作为不可达标记是安全的。
4. 枚举顺序：按 `mask` 从小到大枚举，保证每个状态只被前面的状态更新一次，无需递归或记忆化搜索。