LeetCode 1494. 并行课程 II

Categories:

题目描述
思路分析
1. 解法一：状态压缩 DP（推荐）
相似题目

题目描述

✅ 1494. 并行课程 II

思路分析

解法一：状态压缩 DP（推荐）

核心思路：

用 bitmask 表示已完成课程集合。

对每个状态计算当前可选课程集合，然后枚举其子集（大小 <= k）。

取最小学期数。

复杂度分析：

时间复杂度：O(3^n)，其中 n <= 15。

空间复杂度：O(2^n)。

import java.util.Arrays;

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

        int total = 1 << n;
        int[] dp = new int[total];
        Arrays.fill(dp, n);
        dp[0] = 0;

        for (int mask = 0; mask < total; mask++) {
            int available = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 && (pre[i] & mask) == pre[i]) {
                    available |= 1 << i;
                }
            }

            int subset = available;
            while (subset > 0) {
                if (Integer.bitCount(subset) <= k) {
                    dp[mask | subset] = Math.min(dp[mask | subset], dp[mask] + 1);
                }
                subset = (subset - 1) & available;
            }
        }

        return dp[total - 1];
    }
}

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	pre := make([]int, n)
	for _, r := range relations {
		pre[r[1]-1] |= 1 << (r[0] - 1)
	}

	total := 1 << n
	dp := make([]int, total)
	for i := 1; i < total; i++ {
		dp[i] = n
	}

	for mask := 0; mask < total; mask++ {
		available := 0
		for i := 0; i < n; i++ {
			if (mask&(1<<i)) == 0 && (pre[i]&mask) == pre[i] {
				available |= 1 << i
			}
		}

		subset := available
		for subset > 0 {
			if bitsCount(subset) <= k {
				next := mask | subset
				if dp[mask]+1 < dp[next] {
					dp[next] = dp[mask] + 1
				}
			}
			subset = (subset - 1) & available
		}
	}

	return dp[total-1]
}

func bitsCount(x int) int {
	count := 0
	for x > 0 {
		x &= x - 1
		count++
	}
	return count
}

相似题目

题目	难度	考察点
1494. 并行课程 II	困难	状态压缩 DP
113. 路径总和 II	中等	DFS
207. 课程表	中等	拓扑排序
210. 课程表 II	中等	拓扑排序
1004. 最大连续 1 的个数 III	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/59624894