LeetCode 题解工作台
有向无环图中合法拓扑排序的最大利润
给你一个由 n 个节点组成的 有向无环图（DAG） ，节点编号从 0 到 n - 1 ，通过二维数组 edges 表示，其中 edges[i] = [u i , v i ] 表示一条从节点 u i 指向节点 v i 的有向边。每个节点都有一个对应的 得分 ，由数组 score 给出，其中 score…
6
题型
0
代码语言
3
相关题
当前训练重点
困难 · 动态·规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 动态·规划 题型思路
题目描述
给你一个由 n 个节点组成的有向无环图（DAG），节点编号从 0 到 n - 1，通过二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示一条从节点 ui 指向节点 vi 的有向边。每个节点都有一个对应的 得分 ，由数组 score 给出，其中 score[i] 表示节点 i 的得分。
你需要以 有效的拓扑排序 顺序处理这些节点。每个节点在处理顺序中被分配一个编号从 1 开始的位置。
将每个节点的得分乘以其在拓扑排序中的位置，然后求和，得到的值称为 利润。
请返回在所有合法拓扑排序中可获得的 最大利润 。
拓扑排序 是一个对 DAG 中所有节点的线性排序，使得每条有向边 u → v 中，节点 u 都出现在 v 之前。
示例 1：
输入： n = 2, edges = [[0,1]], score = [2,3]
输出： 8
解释：
节点 1 依赖于节点 0，因此一个合法顺序是 [0, 1]。
| 节点 | 处理顺序 | 得分 | 乘数 | 利润计算 |
|---|---|---|---|---|
| 0 | 第 1 个 | 2 | 1 | 2 × 1 = 2 |
| 1 | 第 2 个 | 3 | 2 | 3 × 2 = 6 |
所有合法拓扑排序中可获得的最大总利润是 2 + 6 = 8。
示例 2：
输入： n = 3, edges = [[0,1],[0,2]], score = [1,6,3]
输出： 25
解释：
节点 1 和 2 都依赖于节点 0，因此最优的合法顺序是 [0, 2, 1]。
| 节点 | 处理顺序 | 得分 | 乘数 | 利润计算 |
|---|---|---|---|---|
| 0 | 第 1 个 | 1 | 1 | 1 × 1 = 1 |
| 2 | 第 2 个 | 3 | 2 | 3 × 2 = 6 |
| 1 | 第 3 个 | 6 | 3 | 6 × 3 = 18 |
所有合法拓扑排序中可获得的最大总利润是 1 + 6 + 18 = 25。
提示：
1 <= n == score.length <= 221 <= score[i] <= 1050 <= edges.length <= n * (n - 1) / 2edges[i] == [ui, vi]表示一条从ui到vi的有向边。0 <= ui, vi < nui != vi- 输入图 保证 是一个 DAG。
- 不存在重复的边。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to represent the graph efficiently.
- question_mark
Check if the candidate is familiar with dynamic programming and bitmasking for subset problems.
- question_mark
Observe the candidate's approach to maximizing profit using node positions in a topological sort.
常见陷阱
外企场景- error
Misunderstanding the need for a valid topological order, leading to incorrect node placements.
- error
Not efficiently calculating the profit for each node in relation to its position in the order.
- error
Overcomplicating the bitmask dynamic programming approach or failing to implement it correctly.
进阶变体
外企场景- arrow_right_alt
Consider adding a constraint where each node has multiple outgoing edges, increasing complexity.
- arrow_right_alt
Implement the problem with additional edge weights, where the profit calculation also depends on edge values.
- arrow_right_alt
Introduce a constraint where not all nodes must be processed, but a subset of nodes should be considered for the topological order.