两道入门题目:

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] 即 所有孩子将饼干全部分完时每个孩子最大饼干数的最小值

代码如下:

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. 完成所有工作的最短时间

代码如下:

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] 状态转移

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] 表示考虑所有桶,把所有元素分配完的所求量为多少