给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 dependencies 中， dependencies[i] = [xi, yi] 表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。
在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
输入：n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2 输出：3 解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/parallel-courses-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int[] mask=new int[15];
int[] dp=new int[1<<15];
int[] cnt=new int[1<<15];
//dp[state] 表示上完状态为state的课程需要多少学期 state第n位为1 则说明课程n已经上过了
//state第n位为0 则说明课程n还没上过
//mask[i] 表示课程i需要先修课程的掩码 mask[i]第j位为1说明 第j门课是i的先修课程 为0 则说明第j门课不是i的先修课程
//cnt[state] 表示状态state中1的个数 也就是state下已完成课程的数目
public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
int N=1<<n;
for(int i=0;i<n;i++) mask[i]=0;
//只需记录上一级的先修课程 先修课程的先修课程不需要记录
//因为只有先修课程的先修课程上完 先修课程才能上
for(int[] d:dependencies) mask[d[1]-1] |=1<<(d[0]-1);
cnt[0]=0;
for(int i=1;i<N;i++) cnt[i]=cnt[i>>1]+(i&1);
for(int i=1;i<N;i++) dp[i]=16; //天数最多为15
dp[0]=0;
for(int i=0;i<N;i++)
{
if(dp[i]<=n) //上完所有课最多需要n学期 如果dp[i]>n 说明i状态无法达到
{
//System.out.print(i+" ");
// i为所有课程的完成状态 j为课程序号
//(i>>j& 0x1)==0 表示i的第j位不是1说明 该课程还没有上
//(mask[j] & i) == mask[j] 说明课程j的先修课程已经上完(i中对应mask[j]所有为1的bit也为1)
//上述条件满足的情况下 将cur的第j位置1 说明该课程可以在当前学期完成
int cur=0;
for(int j=0;j<n;j++)
{
if( (i>>j& 0x1)==0 && (mask[j] & i) == mask[j] ) cur|=1<<j;
}
//l中包括了当前学期内所有可以完成的课程 其中的课程可以选择在本学期完成 也可以不在
// j-1 & l 表示逐步将l中的1从低位开始 每次迭代减少一个(课程)
//当前状态j中的课程数o[j]小于k 说明可以在本学期完成 因此将j中课程加入原始状态i( i|j )
//dp[i]+1 表示学习天数增加一天
for(int j=cur;j!=0;j=j-1&cur)
{
if(cnt[j]<=k) dp[i|j]=Math.min(dp[i|j],dp[i]+1);
}
}
}
return dp[N-1];
}
}