花花酱 LeetCode 1494. Parallel Courses II

Given the integer n representing the number of courses at some university labeled from 1 to n, and the array dependencies where dependencies[i] = [xi, yi]  represents a prerequisite relationship, that is, the course xi must be taken before the course yi.  Also, you are given the integer k.

In one semester you can take at most k courses as long as you have taken all the prerequisites for the courses you are taking.

Return the minimum number of semesters to take all courses. It is guaranteed that you can take all courses in some way.

Example 1:

Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3 
Explanation: The figure above represents the given graph. In this case we can take courses 2 and 3 in the first semester, then take course 1 in the second semester and finally take course 4 in the third semester.

Example 2:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 
Explanation: The figure above represents the given graph. In this case one optimal way to take all courses is: take courses 2 and 3 in the first semester and take course 4 in the second semester, then take course 1 in the third semester and finally take course 5 in the fourth semester.

Example 3:

Input: n = 11, dependencies = [], k = 2
Output: 6

Constraints:

• 1 <= n <= 15
• 1 <= k <= n
• 0 <= dependencies.length <= n * (n-1) / 2
• dependencies[i].length == 2
• 1 <= xi, yi <= n
• xi != yi
• All prerequisite relationships are distinct, that is, dependencies[i] != dependencies[j].
• The given graph is a directed acyclic graph.

Solution: DP / Bitmask

NOTE: This is a NP problem, any polynomial-time algorithm is incorrect otherwise P = NP.

Variant 1:
dp[m] := whether state m is reachable, where m is the bitmask of courses studied.
For each semester, we enumerate all possible states from 0 to 2^n – 1, if that state is reachable, then we choose c (c <= k) courses from n and check whether we can study those courses.
If we can study those courses, we have a new reachable state, we set dp[m | courses] = true.

Time complexity: O(n*2^n*2^n) = O(n*n^4) <– This will be much smaller in practice.
and can be reduced to O(n*3^n).
Space complexity: O(2^n)

Variant 2:
dp[m] := min semesters to reach state m.
dp[m | c] = min{dp[m | c], dp[m] + 1}, if we can reach m | c from m.
This allows us to get rid of enumerate n semesters.
Time complexity: O(2^n*2^n) <– This will be much smaller in practice.
and can be reduced to O(3^n).
Space complexity: O(2^n)