LC-3530 Hard LeetCode

3530. Maximum Profit from Valid Topological Order in DAG

Array Dynamic Programming Bit Manipulation Graph Topological Sort Bitmask

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 26% Topics: Array, Dynamic Programming, Bit Manipulation, Graph, Topological Sort, Bitmask

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n * 2^n)
# Space: O(2^n)

# dp, bitmasks
class Solution(object):
    def maxProfit(self, n, edges, score):
        """
        :type n: int
        :type edges: List[List[int]]
        :type score: List[int]
        :rtype: int
        """
        def popcount(x):
            return bin(x).count('1')

        adj = [0]*n
        for i, j in edges:
            adj[j] |= 1<<i
        dp = [-1]*(1<<n)
        dp[0] = 0 
        for mask in xrange(1<<n):
            if dp[mask] == -1:
                continue
            l = popcount(mask)+1
            for i in xrange(n):
                if mask&(1<<i):
                    continue
                if (mask & adj[i]) == adj[i]: 
                    dp[mask|(1<<i)] = max(dp[mask|(1<<i)], dp[mask]+l*score[i])
        return dp[-1]

Solution from kamyu104/LeetCode-Solutions · MIT