题目描述

//状态压缩dp
//f[state]表示已选择的课程为state的所有集合中，最小的学期
//更新方式：从未被选择的课程中，且入读为0的集合中选择k门课
//f[state|now]=min(f[state|now],f[state]+1);
//思路：
//1.外循环首先从小到大枚举所有状态
//2.内部首先找到可以上的课，然后从中任选K门课，这个可以使用dfs搜索一下
//整个时间复杂度为：
//2^15*(dfs的时间)

class Solution {
public:
    vector<int>f;
    int minNumberOfSemesters(int n, vector<vector<int>>& edges, int k) {


        for(auto &e:edges) e[0]--,e[1]--;//状态压缩是从0开始的
        //状态初始化
        const int INF=100;
        f=vector<int>(1<<n,INF);
        f[0]=0;

        for(int i=0;i<1<<n;i++){//枚举状态
            vector<bool>st(n);//可供选择选课的集合
            for(auto &e:edges)
            {   
                int x=e[0],y=e[1];
                if(!(i>>x&1))//表示x在之前没有被选过，那么y就不能放在备选集合中
                    st[y]=true;//j不能被选择
            }

            //从可以选择的课中找出所有能选择的
            int state=0;
            for(int j=0;j<n;j++){
                if(!st[j]&&!(i>>j&1))//j可以选择，并且没被选过
                    state+=1<<j;
            }
            dfs(n,k,i,state,0,0);
        }
        return f[(1<<n)-1];
    }
    void dfs(int n,int k,int i,int state,int now,int start){//start 表示枚举课程的起点，防止重复枚举
        if(!k||!state){
            f[i|now]=min(f[i|now],f[i]+1);
            return;
        }
        for(int j=start;j<n;j++){
            if(state>>j&1) //如果备选集合中有这门课的话
                dfs(n,k-1,i,state-(1<<j),now+(1<<j),j+1);
        }
    }
};