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

以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 Java 实现。思路概述- n ≤ 22使用状压 DPBitmask DP。- need[i]节点 i 的所有直接前驱的位掩码必须排在 i 之前的节点集合。- dp[mask]已经选了 mask 中这些节点能获得的最大利润。- 转移时已选节点数为 popcount(mask)下一个位置为 pos bitCount 1。枚举所有不在 mask 中且所有前驱都已选的节点 i更新 dp[mask | (1i)]。- 最终答案为 dp[(1n) - 1]。复杂度- 时间O(2^n · n)由于 n ≤ 22约为 2200 万级别可过。- 空间O(2^n)完整代码javaclass 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-basedfor (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 从小到大枚举保证每个状态只被前面的状态更新一次无需递归或记忆化搜索。