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

思路概述

- `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)`

完整代码

```rust
impl Solution {
    pub fn max_profit(n: i32, edges: Vec<Vec<i32>>, score: Vec<i32>) -> i32 {
        let n = n as usize;
        let max_mask = 1 << n;
        
        // need[i] = 节点 i 的所有前驱节点的位掩码
        let mut need = vec![0; n];
        
        // dp[mask] = 已选 mask 中节点时的最大利润
        let mut dp = vec![-1; max_mask];
        dp[0] = 0;
        
        // 构建前驱掩码
        for edge in edges {
            let u = edge[0] as usize;
            let v = edge[1] as usize;
            need[v] |= 1 << u;
        }
        
        for mask in 0..max_mask {
            if dp[mask] == -1 {
                continue;
            }
            
            let pos = (mask.count_ones() + 1) as i32; // 下一个位置（1-based）
            
            for i in 0..n {
                // i 不在 mask 中，且 i 的所有前驱都已在 mask 中
                if (mask & (1 << i)) == 0 && (need[i] & mask) == need[i] {
                    let next_mask = mask | (1 << i);
                    dp[next_mask] = dp[next_mask].max(dp[mask] + score[i] * pos);
                }
            }
        }
        
        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.count_ones() + 1`，因为 `mask` 中已有 `count_ones()` 个节点，下一个节点自然排在第 `count_ones() + 1` 位。
3. DP 初始化：`dp[0] = 0`，其余为 `-1` 表示不可达。由于 `score[i] ≥ 1` 且 `pos ≥ 1`，利润恒为正，`-1` 作为不可达标记是安全的。
4. 枚举顺序：按 `mask` 从小到大枚举，保证每个状态只被前面的状态更新一次。