wkw

Posted on

# [LeetCode The Hard Way] 1494. Parallel Courses II (DP + Bit Manipulation)

Please check out LeetCode The Hard Way for more solution explanations and tutorials. If you like it, please give a star and watch my Github Repository.

``````class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
// dp[i] : the minimum number of semesters needed to take the courses with the bit set in i
// the worst case is that in each semester we can only take one course, hence initialise with `n`
// at the end, the answer would be dp[(1 << n) - 1], i.e. all bits set
vector<int> dp(1 << n, n);
// if the i-th bit is set in pre[j],
// that means we need to take course i in order to take course j
vector<int> pre(n);
// build the prerequisites
for (auto& x : dependencies) {
// make it 0-based index
--x[0], --x[1];
// set the bit at x[0]-th place
pre[x[1]] |= 1 << x[0];
}
// base case: 0 semester. 0 course.
dp[0] = 0;
// i is a set of courses that we've already studied
for (int i = 0; i < (1 << n); i++) {
// init can as 0 to record how can courses we can study
int can = 0;
// iterate all courses
for (int j = 0; j < n; j++) {
// check if we've studied prerequisite courses
if ((pre[j] & i) == pre[j]) {
// if so, we can study course j
can |= (1 << j);
}
}
// remove those courses that we've already studied
can &= ~i;
// enumerate all the bit 1 combinations of `can`
// i.e. all subsets of a bit representation
for (int s = can; s ; s = (s - 1) & can) {
// check if we can take __builtin_popcount(s) courses
if (__builtin_popcount(s) <= k) {
// if so, we combine the previous results (what've studied already)
// or we take a new semester
dp[i | s] = min(dp[i | s], dp[i] + 1);
}
}
}
// same as dp[(1 << n) - 1]
return dp.back();
}
};
``````