[leetcode 1986][状压DP]完成任务的最少工作时间段

题目链接

leetcode 1986 完成任务的最少工作时间段

解题思路

首先声明一个数组sum并做预处理，sum[i]表示当前i对应二进制位为1的任务需要消耗的时间和,例如sum[0B1101]表示完成第1、3、4个任务总共需要的时间

1
2
3
4
5
6
for i := 1; i < len(tasks); i++ {
    m := 1 << i
    for j := range m {
        sum[m|j] = sum[j] + tasks[i]
    }
}

处理好后再声明一个dp，dp[i]表示完成当前i对应二进制位为1的任务最小需要的时间段数量，例如dp[0B1001]表示完成第一个和第四个任务需要的最小时间段数量。对于每个dp[i]，可以枚举i的所有非空子集以表示最后一个时间段完成的工作，例如对于dp[0B1011]就可以枚举0B1011,0B0011,0B1001,0B1010,0B1000,0B0010,0B0001。若当前子集的时间和不超过sessionTime就可以尝试将其作为最后一个时间段,所以dp[i]=min(dp[i^1]+1, dp[dpi^2]+1, ..., dp[i^i]+1)，i^j(j为i的非空子集)表示j的补集

1
2
3
4
5
6
7
8
9
10
11
12
13
   var n = 1 << len(tasks) //n-1则表示所有任务完成的状态
var dp = make([]int, n)
dp[0] = 0
for i := 1; i < n; i++ {
	dp[i] = len(tasks)
       //(j-1)&i始终为小于j的最大子集
	for j := i; j > 0; j = (j - 1) & i {
		if sum[j] <= sessionTime {
			dp[i] = min(dp[i^j]+1, dp[i])
		}
	}
}
return dp[n-1]