上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
}
};
cpp 解法, 执行用时: 424 ms, 内存消耗: 12.2 MB, 提交时间: 2023-06-16 09:36:03
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
vector<int> prerequisite(n, 0);
for (const auto& pair : relations) {
int pre = pair[0] - 1;
int after = pair[1] - 1;
// 举例：prerequisite[1] = 0110 表示1的先修课为2和3
prerequisite[after] |= 1<<pre;
}
int totalState = 1 << n;
vector<int> dp(totalState, 16);
// 0为不需要上任何课的状态，因此不需要学期
dp[0] = 0;
vector<int> cnt(totalState);
cnt[0] = 0;
// 小技巧，计算每个数字的二进制数中，1的个数
for (int i = 1; i < totalState; ++i) {
cnt[i] = cnt[i>>1] + (i&1);
}
// taken表示已经上过的课，假设taken = 0111，表示课程1 2 3已经上过了
for (int taken = 0; taken < totalState; ++taken) {
if (dp[taken] > n) continue;
int cur = 0;
// 在上过taken的基础上，还有哪些课可以上，要满足两个条件
// 1. ((taken & (1 << j)) == 0) 表示这个课在taken中没上过
// 2. ((prerequisite[j] & taken) == prerequisite[j]) 表示这个课的先修课已经上完了
for (int j = 0; j < n; ++j) {
if (((taken & (1 << j)) == 0) && ((prerequisite[j] & taken) == prerequisite[j])) {
// 存这学期可以上的课，注意，可以上不代表一定要上，也不一定要上满，这题的本质是NPC问题，任何贪心的思想都是错的，选择cur中的课来上的这个操作，用下面枚举子集的方法实现
cur |= (1 << j);
}
}
// 枚举cur的子集，比如cur = 111，它的子mask集合就是{111, 110, 101 011, 100, 010, 001}
for (int subMask = cur; subMask != 0; subMask = subMask-1 & cur) {
// 这学期上的课的数量不能超过k
if (cnt[subMask] <= k) {
// 之前上完taken，这学期再上subMask，看看会不会更好
dp[taken|subMask] = min(dp[taken|subMask], dp[taken] + 1);
}
}
}
return dp[totalState - 1];
}
};
python3 解法, 执行用时: 4260 ms, 内存消耗: 17.5 MB, 提交时间: 2023-06-16 09:33:01
class Solution:
def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
dp = [inf] * (1 << n)
need = [0] * (1 << n)
for edge in relations:
need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1)
dp[0] = 0
for i in range(1, (1 << n)):
need[i] = need[i & (i - 1)] | need[i & (-i)]
if (need[i] | i) != i: # i 中有任意一门课程的前置课程没有完成学习
continue
sub = valid = i ^ need[i] # 当前学期可以进行学习的课程集合
if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集
dp[i] = min(dp[i], dp[i ^ sub] + 1)
else: # 枚举子集
while sub:
if sub.bit_count() <= k:
dp[i] = min(dp[i], dp[i ^ sub] + 1)
sub = (sub - 1) & valid
return dp[-1]
javascript 解法, 执行用时: 228 ms, 内存消耗: 47.7 MB, 提交时间: 2023-06-16 09:32:39
/**
* @param {number} n
* @param {number[][]} relations
* @param {number} k
* @return {number}
*/
var minNumberOfSemesters = function(n, relations, k) {
const dp = new Array(1 << n).fill(Infinity);
const need = new Array(1 << n).fill(0);
for (const edge of relations) {
need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1);
}
dp[0] = 0;
for (let i = 1; i < (1 << n); ++i) {
need[i] = need[i & (i - 1)] | need[i & (-i)];
if ((need[i] | i) !== i) {
continue;
}
const valid = i ^ need[i];
if (bitCount(valid) <= k) {
dp[i] = Math.min(dp[i], dp[i ^ valid] + 1);
} else {
for (let sub = valid; sub; sub = (sub - 1) & valid) {
if (bitCount(sub) <= k) {
dp[i] = Math.min(dp[i], dp[i ^ sub] + 1);
}
}
}
}
return dp[(1 << n) - 1];
}
function bitCount(n) {
let count = 0;
while (n) {
count++;
n &= n - 1;
}
return count;
}
golang 解法, 执行用时: 44 ms, 内存消耗: 6.3 MB, 提交时间: 2023-06-16 09:32:16
func minNumberOfSemesters(n int, relations [][]int, k int) int {
dp := make([]int, 1 << n)
for i := range dp {
dp[i] = math.MaxInt32
}
need := make([]int, 1<<n)
for _, edge := range relations {
need[1 << (edge[1] - 1)] |= 1 << (edge[0] - 1)
}
dp[0] = 0
for i := 1; i < (1 << n); i++ {
need[i] = need[i & (i - 1)] | need[i & -i]
if (need[i] | i) != i { // i 中有任意一门课程的前置课程没有完成学习
continue;
}
valid := i ^ need[i]; // 当前学期可以进行学习的课程集合
if bits.OnesCount(uint(valid)) <= k { // 如果个数小于 k，则可以全部学习，不再枚举子集
dp[i] = min(dp[i], dp[i ^ valid] + 1)
} else {
for sub := valid; sub > 0; sub = (sub - 1) & valid {
if bits.OnesCount(uint(sub)) <= k {
dp[i] = min(dp[i], dp[i ^ sub] + 1)
}
}
}
}
return dp[(1 << n) - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
java 解法, 执行用时: 111 ms, 内存消耗: 42.2 MB, 提交时间: 2023-06-16 09:31:50
class Solution {
public int minNumberOfSemesters(int n, int[][] relations, int k) {
int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE);
int[] need = new int[1 << n];
for (int[] edge : relations) {
need[(1 << (edge[1] - 1))] |= 1 << (edge[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) { // i 中有任意一门课程的前置课程没有完成学习
continue;
}
int valid = i ^ need[i]; // 当前学期可以进行学习的课程集合
if (Integer.bitCount(valid) <= k) { // 如果个数小于 k，则可以全部学习，不再枚举子集
dp[i] = Math.min(dp[i], dp[i ^ valid] + 1);
} else { // 否则枚举当前学期需要进行学习的课程集合
for (int sub = valid; sub > 0; sub = (sub - 1) & valid) {
if (Integer.bitCount(sub) <= k) {
dp[i] = Math.min(dp[i], dp[i ^ sub] + 1);
}
}
}
}
return dp[(1 << n) - 1];
}
}
java 解法, 执行用时: 300 ms, 内存消耗: 41.8 MB, 提交时间: 2023-06-16 09:28:43
/**
* 状态压缩dp
*
**/
class Solution {
public int minNumberOfSemesters(int n, int[][] relations, int k) {
int[] pre = new int[n];
for(int[] relation:relations){
//1. 因为点编号是1到n,所以对应于0到n-1的数组，映射位置应为 i-1
//2. 使用状压代表课程先修
pre[relation[1]-1]|=1<<(relation[0]-1);
}
int max = 1 << n;
int [] dp = new int[max];
Arrays.fill(dp,n);
dp[0]=0;
//3. 枚举学习课程的已经学习情况
for(int learned = 0; learned < max; learned++){
//4. 枚举当前学习情况，后续可学习的可能情况
int waitStudy = 0;
for(int i = 0; i < n; i++){
if((pre[i]&learned)==pre[i])
waitStudy |= 1 << i;
}
//细节1. 枚举可学课程需要排除已学课程
waitStudy = waitStudy & (~learned);
//5. 枚举当前1的位置的子集（包含自身），然后用 当前课程= (当前课程-1)&所有可学课程,这种方式，循环找到所有课程枚举子集
for(int learnTerm = waitStudy; learnTerm>0; learnTerm = (learnTerm-1)&waitStudy){
//细节2. 枚举选择的本轮课程需要排除掉一轮学习可能超过最大目标课程的情况
if(Integer.bitCount(learnTerm)>k)
continue;
dp[learned|learnTerm] = Math.min(dp[learned|learnTerm],dp[learned]+1);
}
}
return dp[max-1];
}
}
