力扣 5856. 完成任务的最少工作时间段

题目来源：https://leetcode-cn.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/

大致题意：

给定一个任务耗时数组和一个任务周期。 一个任务只能在一个任务周期中完成，如何分配任务可以得到最少的任务周期。任务周期大于等于单个任务耗时的最大值。

思路

状态DP

令 n 为总任务个数。
使用一个长度为 n 的二进制数来表示分配方案，其中从低位到高位，第 i 位 若为 1，则代表 task[i] 在当前方案中。
那么再使用 dp[x] 表示：分配方案为 x 时的任务周期数。初始时都可以设置为最大值。
接下来，

1. 先使用一轮遍历，遍历所有的分配方案，将可以在一个任务周期中完成的任务标记出来（即dp[x] = 1）
2. 再遍历所有的分配方案，对于每个分配方案，遍历它的子集，看能否做优化。即将当前分配方案分割成子集与子集的补集后，是否需要的任务周期数更少。
3. 返回dp[1 << n - 1]

代码：

public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        // 使用状态压缩，n位的二进制数表示目前的分配方案
        // 其中从低位到高位，第 i 位 若为 1，则代表 task[i] 在当前方案
        int m = 1 << n;
        // 给出一个默认的最大值
        final int INF = 15;
        int[] dp = new int[m];
        // 初始化为最大值
        Arrays.fill(dp, INF);
        // 一轮遍历出可以在一个时间段解决的分配方案
        for (int i = 0; i < m; i++) {
            int state = i;
            int idx = 0;
            int cost = 0;
            while (state > 0) {
                // 当前尾部是否为1，为1代表子集有当前位
                int choice = state & 1;
                // 将当前位的耗时加入
                if (choice == 1) {
                    cost += tasks[idx];
                }
                idx++;
                state >>= 1;
            }
            // 花费小于sessionTime，代表可以在一个时间段做完该子集
            if (cost <= sessionTime)
                dp[i] = 1;
        }
        
        // 第二轮做优化
        for (int i = 0; i < m; i++) {
            // 若当前分配方案已经是最优解：可在一个时间周期解决
            // 直接跳过
            if (dp[i] == 1) {
                continue;
            }
            // 遍历当前分配方案的所有子集，看能否有更优的分配方式
            // j = (j - 1) & i，可以将 j 逐渐变成 i 的子集
            for (int j = i; j > 0; j = (j - 1) & i) {
                // j 是 i 的子集，j ^ i 即是 子集 j 对于 i 的补集
                // 即 j 和 j^i 的并集是 i
                // 若两子集的分配方案优于当前方案，则替换
                dp[i] = Math.min(dp[i], dp[j] + dp[i^j]);
            }
        }
        // 返回最终所有任务都选中的分配方案
        return dp[m-1];
    }

收获

状态压缩后的遍历方法

即遍历当前状态子集的方法：

// m 为 n位的二进制状态
for (int i = 0; i < m; i++) {
		// 遍历当前状态 i 的所有子集状态
        for (int j = i; j > 0; j = (j-1) & i)
}