以下是 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` 从小到大枚举，保证每个状态只被前面的状态更新一次，无需递归或记忆化搜索。