两道入门题目：

1.2305. 公平分发饼干

1.状态定义:dp[i][j] 为第 i个孩子分饼干状态为 j 时每个孩子能分到的最多饼干数的最小值

2.状态转移:要求得dp[i][j] 的值，要考虑 j 的每个子集，再维护 子集计算出的最大值然后转移过来 最小值

​ dp[i][j]=min(max(dp[i-1][j-x],sum[x])) 其中sum[x]为分配状态为 x 时的总的糖果数

3.初始化:dp[0][j]=sum[j]，只分给第一个孩子肯定是全分了总数就是饼干数sum[j]，其余为 INF 方便覆盖

4.遍历顺序:先i后j最后x,正序

5.返回形式:返回 dp[n-1][mask-1] 即 所有孩子将饼干全部分完时每个孩子最大饼干数的最小值

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int distributeCookies(int[] cookies, int k) {
        int n = cookies.length;
        int mask = 1 << n;
        int[][] dp = new int[k][mask];
        int[] sum = new int[mask];
        for (int i = 1; i < mask; i++) {
            // x为获取的最低位1后面尾随0个数，y为缺位x的差集
            int x = Integer.numberOfTrailingZeros(i), y = i - (1 << x);
            sum[i] = sum[y] + cookies[x];
        }
        // 初始化
        System.arraycopy(sum, 0, dp[0], 0, mask);
        for (int i = 1; i < k; i++) {
            Arrays.fill(dp[i], 0x3f3f3f3f);
        }
        // 遍历状态
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < mask; j++) {
                // 此时j-x就是枚举j的所有子集
                for (int x = j; x != 0; x = (x - 1) & j) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][j - x], sum[x]));
                }
            }
        }
        return dp[k - 1][mask - 1];
    }
}

2.1723. 完成所有工作的最短时间

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        int n = jobs.length;    // n为工作份数
        int mask = 1 << n;  // 工作分配情况数目
        // dp[i][j]表示考虑索引为[0,i]的工人,工作分配情况为j(01010...表示)时每个工人最大工作时间的最小值
        int[][] dp = new int[k][mask];
        // 初始化sum[i] -> 完成状态为i的工作的总时间
        int[] sum = new int[mask];
        // i∈[1,mask-1] 因为sum[0]=0
        for (int i = 1; i < mask; i++) {
            // x为i最低位1后面的尾随0个数,y为与i相比仅仅缺位x位置的状态
            int x = Integer.numberOfTrailingZeros(i), y = i - (1 << x);
            sum[i] = sum[y] + jobs[x];  // 加上缺位的x就是i的时长
        }
        // 初始化dp
        System.arraycopy(sum, 0, dp[0], 0, mask);
        for (int i = 1; i < k; i++) {
            Arrays.fill(dp[i], 0x3f3f3f3f);
        }
        // 遍历dp状态
        // 遍历每个工人i
        for (int i = 1; i < k; i++) {
            // 遍历每种状态j
            for (int j = 0; j < mask; j++) {
                // 遍历状态j的每种子集j-x
                for (int x = j; x != 0 ; x = (x - 1) & j) {
                    // 找到每种子集j-x得到的最大值转移过来的 最小值 就是考虑[0,i]工人,状态为j-x的最大工作时间的最小值
                    // 子集转移途径为:取前面dp[i - 1][j - x]最大值的最小值与分配给工人i的sum[x]进行比较找到最大值
                    // 再维护每种转移途经最小值
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][j - x], sum[x]));
                }
            }
        }
        // 所有工人分配完所有工作的最长单人工作时间最小值
        return dp[k - 1][mask - 1];
    }
}

我们不妨来总结一下状态压缩DP：其实状态压缩DP是类似于暴力法回溯的方法，能用状态压缩方法做的通常都可以用回溯+剪枝来求解。一般来说这种问题称为“分配问题”，或者叫做“桶轮询”。就是将元素(通常数目很小<32个)分配到多个容器(桶)中，然后求解有每个桶最多数目的最少值，或者是满足条件路径数等，这里求解目标的不同体现在转移方程上。

抽象一下：饼干、工作（要分配的对象）——元素；工人、孩子（被分配到的地方）——容器（桶）

526. 优美的排列 这道题就是要求路径数目，同时将桶容量限制为1，因此子集数目只有 i 个

3.总体模板（本质也是DP）：

1.状态定义：dp[i][i]为考虑前 i 个容器（桶），分配状态为 j (0101表示分配状态)时候的 所求量（路径数、最大值、最小值等）

2.状态转移：此时遍历到第 i 个容器（桶），一般来说要求 dp[i][j] 得考虑前面容器的情况 -> dp[i-1][j-x]

其中 x 为第 i 个容器的选择状态，那么 j-x 就是 [0,i-1] 个容器的选择状态

将第i个容器独立出来考虑，这个容器的选择有哪些？也就是转移路径有哪些？？？

很显然如果桶的容量（包括元素个数与总和）没有限制的话，j 的全体子集（除了本身）都是符合要求的前一个状态

-> 因此可以直接通过下面语句枚举 j 的所有合法子集来进行 dp[i][j] 状态转移

1
2
3
for (int x = j; x != 0 ; x = (x - 1) & j) {
    dp[i][j] = dp[i - 1][j - x]... // 搭建两个状态的桥梁
}

-> 当然也有可能容量有限：参考 526. 优美的排列 枚举符合条件的子集（合法转移路径）进行转移即可

3.初始化：一般来说，初始化 dp[0][j] 为首个容器分得状态 j 时的所求量；其他dp[i][j] 按照转移逻辑来初始化

目的都是要作为初始哨兵不影响第一个值的覆盖（如求最大值就弄个很小的数第一个比较的必定顺利覆盖…）

4.遍历顺序：一般是先遍历容器 i ，再遍历每个状态 j ，最后遍历每种合法转移路径 j-x，默认正序

5.返回形式：一般返回 dp[n-1][mask-1] 表示考虑所有桶，把所有元素分配完的所求量为多少