Skip to content

3530. Maximum Profit from Valid Topological Order in DAG 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int maxProfit(int n, vector<vector<int>>& edges, vector<int>& score) {
    const int maxMask = 1 << n;
    // need[i] := the bitmask representing all nodes that must be placed before
    // node i
    vector<int> need(n);
    // dp[mask] := the maximum profit achievable by placing the set of nodes
    // represented by `mask`
    vector<int> dp(maxMask, -1);
    dp[0] = 0;

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      need[v] |= 1 << u;
    }

    // Iterate over all subsets of nodes (represented by bitmask `mask`)
    for (unsigned mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == -1)
        continue;
      // Determine the position of the next node to be placed (1-based).
      const int pos = popcount(mask) + 1;
      // Try to place each node `i` that hasn't been placed yet.
      for (int i = 0; i < n; ++i) {
        if (mask >> i & 1)
          continue;
        // Check if all dependencies of node `i` are already placed.
        if ((mask & need[i]) == need[i]) {
          const int newMask = mask | 1 << i;  // Mark node `i` as placed.
          dp[newMask] = max(dp[newMask], dp[mask] + score[i] * pos);
        }
      }
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public int maxProfit(int n, int[][] edges, int[] score) {
    final int maxMask = 1 << n;
    // need[i] := the bitmask representing all nodes that must be placed before node i
    int[] need = new int[n];
    // dp[mask] := the maximum profit achievable by placing the set of nodes represented by `mask`
    int[] dp = new int[maxMask];
    Arrays.fill(dp, -1);
    dp[0] = 0;

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      need[v] |= 1 << u;
    }

    // Iterate over all subsets of nodes (represented by bitmask `mask`)
    for (int mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == -1)
        continue;
      // Determine the position of the next node to be placed (1-based).
      int pos = Integer.bitCount(mask) + 1;
      // Try to place each node `i` that hasn't been placed yet.
      for (int i = 0; i < n; ++i) {
        if ((mask >> i & 1) == 1)
          continue;
        // Check if all dependencies of node `i` are already placed.
        if ((mask & need[i]) == need[i]) {
          final int newMask = mask | 1 << i; // Mark node `i` as placed.
          dp[newMask] = Math.max(dp[newMask], dp[mask] + score[i] * pos);
        }
      }
    }

    return dp[maxMask - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def maxProfit(self, n: int, edges: list[list[int]], score: list[int]) -> int:
    # need[i] := the bitmask representing all nodes that must be placed before
    # node i
    need = [0] * n
    # dp[mask] := the maximum profit achievable by placing the set of nodes
    # represented by `mask`
    dp = [-1] * (1 << n)
    dp[0] = 0

    for u, v in edges:
      need[v] |= 1 << u

    # Iterate over all subsets of nodes (represented by bitmask `mask`)
    for mask in range(1 << n):
      if dp[mask] == -1:
        continue
      # Determine the position of the next node to be placed (1-based).
      pos = mask.bit_count() + 1
      # Try to place each node `i` that hasn't been placed yet.
      for i in range(n):
        if mask >> i & 1:
          continue
        # Check if all dependencies of node `i` are already placed.
        if (mask & need[i]) == need[i]:
          newMask = mask | 1 << i  # Mark node `i` as placed.
          dp[newMask] = max(dp[newMask], dp[mask] + score[i] * pos)

    return dp[-1]