[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();
    }
};