子集状压DP

本来应该放到DP篇。但由于这个部分灵神单列了题单，我就按题单刷题记录单列一篇。位运算状压应该算是我入门第一个接触到的算法级别的trick。

详细的位运算trick参考灵神的详解：leetcode.cn/circle/discuss/CaOJ45/

知识图谱也列出来了：

因此本篇会略过位运算，仅将其作为工具。主要还是子集DP。

1. 周赛297 LC 2305 公平分发饼干

这题灵神标的1887。甚至不到K。但由于我压根没学过状压，这题就烂掉了。

另外DP是我的尤其弱项，基本很少有能靠自己想出来的，想出来的也基本都是板子题。一次双周赛118 T3的状态机DP，一次周赛377的floyd板子，还有一次忘了哪次双周赛出了个特别特别板的子集DP，算法导论课作业有过这题，大致就是问从一个集合中选取子集，能否组成某个目标值。这题是板中之板，刷烂了的题。只有这种很板或者很简单的DP我才能自己想出来，不然就是直接烂。

这题我一开始压根想不到DP，最小化最大值一眼二分板子，但是检查不会写，写了个贪心。然后WA。反例如下：

[15,18,19,5,6,13,15,20]
3

我是从大到小贪心选择的，过不了。感觉任何贪心都过不了，这就不是贪心题。另外二分可以用但没必要，直接可以DP求解的题没必要转判定。

现在进入正题，子集状压DP。

可以将题意理解为：将整个集合划分为k个子集，求所有划分方式中K个集合各自元素和最大值的最小值。（我在LC上做DP到现在，大几十题了，感觉DP最大的难点不是写状态转移方程，而是设计状态含义，这需要对题目有最本质的理解才能做到，很多时候我就是看不出题目的本质，DP设计不出。灵神的思路和视角一直都是直击本质的，看他做搜索题是一种享受）

令f[i][j]表示对于集合j，将其划分为i个子序列，所有划分方式中i个子序列元素和的最大值的最小值。

思路是枚举j的子集s，遍历每一种划分情况带来的代价（这个代价当然是一个最大值），然后取这些代价中的最小值。

1. 枚举j的子集s，s 是 j 的一个子集，它有一个元素和 sum(s)
2. 而目标的f[i][j]希望能有i个子集，现在我们单独计算了s这个子集，那么还有i-1个子集
3. 这些子集可选的元素需要剔除掉s中的元素：j^s(^s代表异或，是位运算中的差集trick）
4. 对于每种不同的划分{s,j^s} 都会产生一个子集元素和的最大值，那么我们的目的就是求这些最大值中的最小值
5. 状态转移方程为：min ( max ( sum(s) , f[i-1][j^s] ) ) for s in j
6. 由于我们想求的是将整个集合划分为k个子集的最小代价，那么答案就是f[k-1][(1<<n)-1]了。

在实现上，可以预先计算所有的子集和，这样之后要用sum(s)的时候直接查表就可以，这里就涉及到**判断子集元素**的技巧：

1. 状压：1 << n
2. 枚举：for i in (1 << n) for j in(1,n)
3. 位与判断是否在该子集中：i>>j&1

另外还有枚举j的子集s，这涉及**枚举子集**的技巧：

1. s=j
2. s=(s-1)&j
3. 直至s≤0

具体原理的证明就算了。例子在代码里：

import java.util.Arrays;

class Solution {
    public int distributeCookies(int[] cookies, int k) {
        // 题意：将整个集合划分为K个集合，求所有划分方式中K个集合各自元素和的最大值的最小值
        // 输入顺序随意

        // 令f[i][j]表示消耗i个子序列，这i个子序列组成集合j对应的i个集合各自元素和最大值的最小值
        int n = cookies.length;
        // 预先计算每个子集的和用来查表
        // 这里状压，比如 5D = 0101B,代表选取第1个元素和第3个元素(下标为0开始就是第0个和第2个)
        int[] sum = new int[1 << n];
        // 预计算子集和
        // 枚举
        for (int i = 1; i < 1 << n; i++) {
            // 遍历所有cookie，看谁被选中了，i本质上就是状压后的选择结果
            // 比如3个零食包，则共有8个子集，假设现在是0101B好了，说明选择了第0个和第2个零食包。
            // i = 0101B,j=0D->2D
            // i 右移0位，0101B，末尾1说明被选中，第零号零食包选中
            // i 右移1位，0010B，末尾0说明没被选中，第一号零食包没选中
            // i 右移2位，0001B，末尾1说明被选中，第二号零食包选中
            for(int j=0;j<n;j++){
                if((i>>j&1)==1){
                    sum[i]+=cookies[j];
                }
            }
        }

        // 状态转移
        int[][] f = new int[k][1 << n];
        // f[0]实际代表f[1]，消耗一个子序列，f[i]对应上述的f[i+1]，下标从0开始位置错开了
        // f[0]即消耗一个集合，这个集合就是枚举cookies的每一个子集，也就是sum对应的元素和数组
        f[0] = sum;
        // 最终目标f[k-1][1<<n]，即将整个集合划分为k个子集的元素和的最大值的最小值
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < (1 << n); j++) {
                // 这里状压，枚举j的子集
                // x & (x-1)
                // 例如求10110B的子集
                // 10110B-1B = 10101B
                // 10101B & 10110B = 10100B 确实是子集
                // 下一个子集从10100B开始
                // 10100B - 1B = 10011B
                // 10011B & 10110B = 10010B 也是子集
                // 这样枚举是不重不漏的
                // 证明就算了
                f[i][j] = (int) 1e9;
                for(int s = j; s > 0 ; s=(s-1)&j){
                    f[i][j] = Math.min(
                            f[i][j],
                            Math.max(sum[s],f[i-1][j^s]) // 差集位运算经典trick异或^
                    );
                }
            }
        }
        return f[k-1][(1<<n)-1];
    }
}

由于状态转移只和前一个f[i-1]有关，就可以滚动数组降空间了：

import java.util.Arrays;

class Solution {
    public int distributeCookies(int[] cookies, int k) {
        int n = cookies.length;
        int[] sum = new int[1 << n];
        for (int i = 1; i < 1 << n; i++) {
            for(int j=0;j<n;j++){
                if((i>>j&1)==1){
                    sum[i]+=cookies[j];
                }
            }
        }

        var f = sum.clone();
        for (var i = 1; i < k; i++) {
            for (var j = (1 << n) - 1; j > 0; j--) {
                for (var s = j; s > 0; s = (s - 1) & j) {
                    f[j] = Math.min(f[j], Math.max(f[j ^ s], sum[s]));
                }
            }
        }
        return f[(1 << n) - 1];
    }
}