1494. Parallel Courses II

class Solution {
    public int minNumberOfSemesters(int n, int[][] relations, int k) {
        int[] pre = new int[n];
        for (int[] relation : relations) {
            pre[relation[1] - 1] |= (1 << (relation[0] - 1));
        }

        int[] dp = new int[1 << n];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for (int state = 0; state < (1 << n); state++) {
            int curMask = 0;
            for (int i = 0; i < n; i++) {
                if (((state & (1 << i)) == 0) && ((pre[i] & state) == pre[i])) {
                    curMask |= (1 << i);
                }
            }

            for (int subMask = curMask; subMask > 0; subMask = subMask - 1 & curMask) {
                if (Integer.bitCount(subMask) > k) continue;
                if (dp[state] + 1 < dp[state | subMask]) {
                    dp[state | subMask] = dp[state] + 1;
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}