https://leetcode.com/problems/parallel-courses-ii/
https://leetcode-cn.com/contest/biweekly-contest-29/problems/parallel-courses-ii/
这是一道DP题目，状态转移方程是
- dp[s|t] = min(dp[s|t], dp[s] + 1)
- s 表示已经完成的课程
- t 表示将要开始的课程
- s,t 必须满足拓扑顺序，也就是t里面所有依赖课程都必须在s里面
- t 中bits的数量必须小于等于k
按照这个思路代码如下，其中：
- dp[s] 表示完成s状态这些课程需要使用的时间
- radj 表示反向依赖. `y in radj[x]` 表示必须先学习完成y才能学习x
inf = 999
ST = 1 << n
dp = [inf] * ST
radj = [[] for _ in range(n)]
for x, y in dependencies:
radj[y - 1].append(x - 1)
dp[0] = 0
for st in range(ST):
# find possible courses.
cs = []
for x in range(n):
if st & (1 << x): continue
ok = True
for y in radj[x]:
if (st & (1 << y)) == 0:
ok = False
if ok:
cs.append(x)
# enumerate possible combinations.
for st2 in walk(cs, k):
st3 = st | st2
dp[st3] = min(dp[st3], dp[st] + 1)接着就是 `walk(cs, k)` 这个函数了，表示从cs里面选择bits小于等于k的组合。我的代码使用了python自带的 `combinations` 函数
def walk(cs, k):
off = len(cs) - k
base = 0
for x in cs:
base = base | (1 << x)
if off <= 0:
yield base
else:
import itertools
for xs in itertools.combinations(cs, off):
st = base
for x in xs:
st = st & ~(1 << x)
yield st这个实现不算糟糕，考虑到了 `len(cs)<=k` 的情况，这样的话就可以直接返回。如果 `len(cs)>k` 的话，那么我们只选择几个需要关闭的bits就行。
但是如果没有 `combinations` 的话(Java/C++)，那就只能通过遍历了。我看比赛中 `liouzhou_101` 的代码比较有参考性。其中：
- can就是我们上面的base
- 从can开始遍历, 肯定会在某些bit上出现不应该出现的1
- 然后在和can做一个and操作，就可以得到正确结果
- 接着我们直接使用这个正确结果继续遍历
for (int t = can; t; t = (t-1)&can) {
if (__builtin_popcount(t) > k) continue;
f[s|t] = min(f[s|t], f[s]+1);
}python里面没有 __builtin_popcount 这样的高效实现，所以拿去提交都是TLE.
def walk(cs, k):
def bitsoncount(x):
c = 0
while x:
if x & 1:
c += 1
x = x >> 1
return c
can = 0
for x in cs:
can = can | (1 << x)
t = can
while t:
if bitsoncount(t) <= k:
yield t
t = (t - 1) & can