两道入门题目：

1.2305. 公平分发饼干 {#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. 完成所有工作的最短时间 {#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）： {#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] 表示考虑所有桶，把所有元素分配完的所求量为多少