1494. 并行课程 II

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xi, yi]  表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。

在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。

请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/parallel-courses-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.Arrays;

class Solution {
    public int minNumberOfSemesters(int n, int[][] relations, int k) {
        int[] dp = new int[1 << n];
        int[] need = new int[1 << n];
        int INF = Integer.MAX_VALUE;
        Arrays.fill(dp, INF);

        for (int[] relation : relations) {
            need[1 << (relation[1] - 1)] |= 1 << (relation[0] - 1);
        }

        dp[0] = 0;
        for (int i = 1; i < 1 << n; i++) {
            need[i] = need[i & (i - 1)] | need[i & (-i)];
            if ((need[i] | i) != i) {
                continue;
            }

            int x = need[i] ^ i;
            if (Integer.bitCount(x) <= k) {
                dp[i] = Math.min(dp[i], dp[need[i]] + 1);
            } else {
                for (int j = x; j > 0; j = (j - 1) & x) {
                    if (Integer.bitCount(j) <= k) {
                        dp[i] = Math.min(dp[i], dp[i ^ j] + 1);
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}