Hard

题目描述

给你一个有 n 个节点的有向无环图（DAG），节点标记为 0 到 n - 1，用二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示从节点 ui 到 vi 的有向边。每个节点都有一个关联的分数，在数组 score 中给出，其中 score[i] 表示节点 i 的分数。

你必须按照有效的拓扑顺序处理节点。每个节点在处理顺序中被分配一个基于 1 的位置。

利润通过将每个节点的分数与其在排序中的位置相乘，然后求和来计算。

返回通过最优拓扑顺序可以实现的最大可能利润。

有向无环图的拓扑顺序是其节点的线性排序，对于每条有向边 u → v，节点 u 在排序中出现在 v 之前。

示例 1：

输入：n = 2, edges = [[0,1]], score = [2,3]
输出：8
解释：节点 1 依赖于节点 0，所以有效顺序是 [0, 1]。
最大总利润为 2 × 1 + 3 × 2 = 8。

示例 2：

输入：n = 3, edges = [[0,1],[0,2]], score = [1,6,3]
输出：25
解释：节点 1 和 2 都依赖于节点 0，最优有效顺序是 [0, 2, 1]。
最大总利润为 1 × 1 + 3 × 2 + 6 × 3 = 25。

约束：

  • 1 <= n == score.length <= 22
  • 1 <= score[i] <= 10^5
  • 0 <= edges.length <= n * (n - 1) / 2
  • edges[i] == [ui, vi] 表示从 ui 到 vi 的有向边
  • 0 <= ui, vi < n
  • ui != vi
  • 输入图保证是 DAG
  • 没有重复的边

解题思路

这道题要求在满足拓扑排序约束的前提下，最大化节点分数与位置的乘积之和。

核心思路： 由于 n ≤ 22，可以使用状态压缩动态规划。用位掩码 mask 表示已经处理过的节点集合，每一位表示对应节点是否已被选择。

算法步骤：

  1. 预处理图的入度信息，构建邻接表
  2. 使用 DFS + 记忆化搜索，状态为 (mask, degrees)
    • mask：已处理节点的位掩码
    • degrees：当前剩余节点的入度数组
  3. 对于每个状态，枚举所有入度为 0 的未处理节点作为下一个选择
  4. 选择某个节点后，更新其后继节点的入度，递归计算剩余节点的最大利润
  5. 当前节点的贡献为 score[node] × position，其中 position 是当前处理的第几个节点

优化点：

  • 使用记忆化避免重复计算相同状态
  • 只考虑入度为 0 的节点，保证拓扑序的合法性
  • 选择分数最大的节点放在后面的位置，获得更大的位置权重

时间复杂度主要取决于状态数量和每个状态的转移次数。

代码实现

class Solution {
public:
    int maxProfit(int n, vector<vector<int>>& edges, vector<int>& score) {
        vector<vector<int>> graph(n);
        vector<int> indegree(n, 0);
        
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
        }
        
        unordered_map<string, int> memo;
        
        function<int(int, vector<int>&)> dfs = [&](int mask, vector<int>& degrees) -> int {
            string key = to_string(mask) + "_" + to_string(hash<vector<int>>{}(degrees));
            if (memo.count(key)) return memo[key];
            
            int processed = __builtin_popcount(mask);
            if (processed == n) return 0;
            
            int maxProfit = 0;
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i)) && degrees[i] == 0) {
                    vector<int> newDegrees = degrees;
                    for (int next : graph[i]) {
                        newDegrees[next]--;
                    }
                    
                    int currentProfit = score[i] * (processed + 1);
                    int futureProfit = dfs(mask | (1 << i), newDegrees);
                    maxProfit = max(maxProfit, currentProfit + futureProfit);
                }
            }
            
            return memo[key] = maxProfit;
        };
        
        return dfs(0, indegree);
    }
};

class Solution:
    def maxProfit(self, n: int, edges: List[List[int]], score: List[int]) -> int:
        from functools import lru_cache
        
        graph = [[] for _ in range(n)]
        indegree = [0] * n
        
        for u, v in edges:
            graph[u].append(v)
            indegree[v] += 1
        
        @lru_cache(maxsize=None)
        def dfs(mask, degrees_tuple):
            degrees = list(degrees_tuple)
            processed = bin(mask).count('1')
            
            if processed == n:
                return 0
            
            max_profit = 0
            for i in range(n):
                if not (mask & (1 << i)) and degrees[i] == 0:
                    new_degrees = degrees[:]
                    for next_node in graph[i]:
                        new_degrees[next_node] -= 1
                    
                    current_profit = score[i] * (processed + 1)
                    future_profit = dfs(mask | (1 << i), tuple(new_degrees))
                    max_profit = max(max_profit, current_profit + future_profit)
            
            return max_profit
        
        return dfs(0, tuple(indegree))

public class Solution {
    public int MaxProfit(int n, int[][] edges, int[] score) {
        var graph = new List<int>[n];
        var indegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            indegree[edge[1]]++;
        }
        
        var memo = new Dictionary<string, int>();
        
        int Dfs(int mask, int[] degrees) {
            string key = mask + "_" + string.Join(",", degrees);
            if (memo.ContainsKey(key)) return memo[key];
            
            int processed = System.Numerics.BitOperations.PopCount((uint)mask);
            if (processed == n) return 0;
            
            int maxProfit = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 && degrees[i] == 0) {
                    var newDegrees = (int[])degrees.Clone();
                    foreach (int next in graph[i]) {
                        newDegrees[next]--;
                    }
                    
                    int currentProfit = score[i] * (processed + 1);
                    int futureProfit = Dfs(mask | (1 << i), newDegrees);
                    maxProfit = Math.Max(maxProfit, currentProfit + futureProfit);
                }
            }
            
            return memo[key] = maxProfit;
        }
        
        return Dfs(0, indegree);
    }
}

var maxProfit = function(n, edges, score) {
    const graph = Array.from({length: n}, () => []);
    const indegree = new Array(n).fill(0);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        indegree[v]++;
    }
    
    const memo = new Map();
    
    function dfs(mask) {
        if (memo.has(mask)) return memo.get(mask);
        
        const remaining = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) continue;
            
            let canProcess = true;
            for (const [u, v] of edges) {
                if (v === i && !(mask & (1 << u))) {
                    canProcess = false;
                    break;
                }
            }
            if (canProcess) remaining.push(i);
        }
        
        if (remaining.length === 0) return 0;
        
        const position = n - __builtin_popcount(mask);
        let maxProfit = 0;
        
        for (const node of remaining) {
            const newMask = mask | (1 << node);
            const profit = score[node] * position + dfs(newMask);
            maxProfit = Math.max(maxProfit, profit);
        }
        
        memo.set(mask, maxProfit);
        return maxProfit;
    }
    
    function __builtin_popcount(x) {
        let count = 0;
        while (x) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
    
    return dfs(0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^n × n^2) - 共有 2^n 种状态，每个状态最多尝试 n 个节点，更新度数需要 O(n)
空间复杂度O(2^n × n) - 记忆化存储的状态数量，每个状态存储度数数组