状压DP

状态压缩动态规划是一种解决小规模问题的有效方法，尽管它本质上是暴力算法。这种方法通过遍历所有可能的状态来找到最优解，而每个状态实际上代表了一组事件的组合。由于集合问题通常具有指数级别的复杂度，属于NP问题范畴，因此状态压缩DP的时间复杂度也是指数级的，这限制了它只能应用于规模较小的问题。

为了高效地表示和处理这些状态，我们常用二进制数来编码。这样一来，一个单一的整数就能够表示整个状态，其中每一位二进制数字都对应着一个特定事件的存在与否。例如，如果有10枚硬币，每枚硬币都有正面或反面两种可能性，那么所有可能的结果就可以用一个10位的二进制数来表示，每一位上的0或1分别代表着该位置上硬币的状态。

使用二进制编码不仅能够极大地减少存储空间的需求，还允许我们利用位运算快速实现状态之间的转换。位运算提供了一种简洁且计算效率高的方式来更新、比较以及操作状态，从而使得状态压缩DP成为解决某些类型优化问题时既紧凑又实用的技术手段。

二进制位变换

下面列举了一些常见的二进制位的变换操作。

技巧	示例	代码实现
去掉最后一位	(101101->10110)	`x >> 1`
在最后加一个0	(101101->1011010)	`x << 1`
在最后加一个1	(101101->1011011)	`x << 1 + 1`
把最后一位变成1	(101100->101101)	`x \| 1`
把最后一位变成0	(101101->101100)	`x \| 1 - 1`
最后一位取反	(101101->101100)	`x ^ 1`
把右数第k位变成1	(101001->101101,k=3)	`x \| (1 << (k - 1))`
把右数第k位变成0	(101101->101001,k=3)	`x & ~(1 << (k - 1))`
右数第k位取反	(101001->101101,k=3)	`x ^ (1 << (k - 1))`
取末k位	(1101101->1101,k=5)	`x & (1 << k - 1)`
取右数第k位	(1101101->1,k=4)	`x >> (k - 1) & 1`
把末k位变成1	(101001->101111,k=4)	`x \| (1 << k - 1)`
末k位取反	(101001->100110,k=4)	`x ^ (1 << k - 1)`
把右起第一个0变成1	(100101111->100111111)	`x \| (x + 1)`
把右起第一个1变成0	(11011000->11010000)	`x & (x − 1)`
把右边连续的0变成1	(11011000->11011111)	`x \| (x - 1)`
把右边连续的1变成0	(100101111->100100000)	`x & (x + 1)`
取右边连续的1	(100101111->1111)	`(x ^ (x + 1)) >> 1`

例题讲解

公平分发饼干

给你一个整数数组 cookies ，其中 cookies[i] 表示在第 i 个零食包中的饼干数量。另给你一个整数 k 表示等待分发零食包的孩子数量，所有零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。
分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。
返回所有分发的最小不公平程度。
提示：
2 <= cookies.length <= 8
1 <= cookies[i] <= 105
2 <= k <= cookies.length

问题理解

任务是将一定数量的饼干包（每个包有特定数量的饼干）分配给几个孩子，目的是让得到最多饼干的那个孩子所拥有的饼干数量最少。这个问题是一个NP完全问题，意味着直接找到最优解通常需要遍历所有可能的分配方式。

算法分析

由于本题规模较小（不超过8个饼干包），我们可以使用状态压缩动态规划来解决这个问题。通过位运算和二进制编码，我们可以高效地表示每个状态并进行状态转移。

核心思想是用一个二进制数表示哪些饼干包已经被分配出去，然后利用递归或迭代方法尝试所有可能的分配组合，最终找出最优解。

实现步骤

初始化

创建一个数组 s 来存储每个可能的状态（即每个子集）下饼干的总和。

对每一个饼干包，更新所有包含该饼干包的状态的总和。

定义 f[i][j] 作为前 i 个孩子在状态 j 下分配饼干后的最小不公平程度。初始时，f[0][j] 就是状态 j 的饼干总和。

状态表示

我们有 n 个零食包，可以用一个 n 位的二进制数 j 来表示这些零食包的状态。
每一位代表一个零食包，如果这一位是 1，则表示该零食包已经被分配出去；如果是 0，则表示还未被分配。
总共有 2^n 种不同的状态，即 1 << n 种可能的状态。

状态转移

假设当前已经为前 k-1 个孩子分配了零食，现在要为第 k 个孩子分配零食。
如果当前状态是 j，那么我们需要从 j 中选择一部分零食包给第 k 个孩子。这部分零食包的状态可以表示为 c，其中 c 是 j 的一个子集。
对于每一个可能的 c，我们可以计算出：
- 分配给第 k 个孩子的零食总数：s[c]
- 剩余未分配给第 k 个孩子的零食状态：j ^ c （^ 表示按位异或操作）
我们需要找到一种分配方式，使得在当前状态下分配给第 k 个孩子后的不公平程度最小。

枚举所有可能的决策

要枚举 j 的所有非空子集 c，可以使用以下技巧：
cpp
```
for (int c = j; c; c = (c - 1) & j) {
    // 处理子集 c
}
```
这段代码会遍历 j 的所有非空子集 c。每次循环中，c 都是一个 j 的子集，直到 c 变为 0。
具体来说，(c - 1) 会将 c 的最低位 1 及其右侧的所有位翻转，而 & j 则确保 c 仍然是 j 的子集。

更新 DP 表

设 f[i][j] 表示将状态 j 下的零食包分配给前 i+1 个孩子后的最小不公平程度。
初始条件是 f[0][j] = s[j]，即当只有一个孩子时，不公平程度就是状态 j 下的总饼干数。
对于每个 i 和 j，我们需要更新 f[i][j] 为：
cpp
```
f[i][j] = min(f[i][j], max(f[i-1][j^c], s[c]));
```
其中 f[i-1][j^c] 表示前 i 个孩子分配完剩余零食包后的最小不公平程度，s[c] 表示第 i 个孩子得到的零食总数。

优化空间复杂度

观察到 f[i][j] 只依赖于 f[i-1][...]，因此可以去掉第一个维度，只保留一维数组 f。
通过倒序枚举状态 j，可以避免覆盖还未处理的状态，从而实现空间上的优化。

代码实现

查看代码

cpp

class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        int n=cookies.size();
        vector<int>s(1<<n); // 表示所有的零食包分发状态的不公平程度
        for(int i=0;i<n;i++){ 
            for(int j=0,c=(1<<i);j<c;j++){ // 将第i个零食包分发到所有子集
                s[j|c]=s[j]+cookies[i];
            }
        }
        vector<vector<int>>f(k,vector<int>(1<<n,INT_MAX)); // f[i][j]表示以零食包分发状态j时分给i个小朋友的最优解
        for(int i=0;i<(1<<n);i++){ // 分给一个小朋友时就是零食包分发状态的不公平程度
            f[0][i]=s[i];
        }
        for(int i=1;i<k;i++){
            for(int j=1;j<(1<<n);j++){
                for(int c=j;c;c=(c-1)&j){ // 将零食包分发状态j分给第i位小朋友
                    f[i][j]=min(f[i][j],max(f[i-1][j^c],s[c]));
                }
            }
        }
        return f[k-1][(1<<n)-1];
    }
};
class Solution {
public:
    int distributeCookies(vector<int>& cookies, int k) {
        int n = cookies.size();
        vector<int> s(1 << n); // 预处理每个状态下的饼干总和

        // 初始化 s 数组
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < (1 << n); ++j) {
                if (j & (1 << i)) { // 如果当前状态包含第 i 个饼干包
                    s[j] = s[j ^ (1 << i)] + cookies[i]; // 更新状态 j 的饼干总和
                }
            }
        }

        vector<int> f(s); // 初始化动态规划表
        for (int i = 1; i < k; ++i) { // 对于每个孩子
            for (int j = (1 << n) - 1; j > 0; --j) { // 倒序遍历所有状态
                for (int c = j; c; c = (c - 1) & j) { // 枚举子集
                    f[j] = min(f[j], max(f[j ^ c], s[c])); // 更新当前状态的最小不公平程度
                }
            }
        }
        return f.back(); // 返回最终结果
    }
};

第二段代码通过预处理每个状态下的饼干总和，并使用动态规划求解最小不公平程度。通过倒序枚举状态 j，我们可以省略 f 数组的第一个维度，从而减少空间复杂度。

最大兼容性评分和

有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。
这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。
每个学生都会被分配给一名导师，而每位导师也会分配到一名学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。
例如，学生答案为[1, 0, 1] 而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。
请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。
给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。
提示：
m == students.length == mentors.length
n == students[i].length == mentors[j].length
1 <= m, n <= 8
students[i][k] 为 0 或 1
mentors[j][k] 为 0 或 1

问题理解

求出使学生和导师答案相同的总次数最多的一种最优配对方案，然后返回总次数。
m 名学生和 m 名导师一一配对，求所有配对方案中，学生和导师答案相同的最多总次数。

算法分析

由于m和n的值相对较小（1 <= m, n <= 8），我们可以采用暴力枚举的方法来解决这个问题。我们将枚举所有可能的配对方案，并计算出每个方案的总兼容性评分，然后从中选出最大的一个。

实现步骤

预处理兼容性评分

计算每对学生与导师之间的兼容性评分，并存储在一个二维数组 g 中，其中 g[i][j] 表示学生 i 和导师 j 的兼容性评分。

状态表示

使用一个 m 位的二进制数 i 来表示导师的分配状态。
如果 i 的第 j 位是 1，则表示导师 j 已经被分配给某个学生；如果是 0，则表示还未被分配。

动态规划

动态规划定义

f[i]：表示在导师分配状态为 i 时，可以得到的最大兼容性评分和。
i：是一个 m 位的二进制数，每一位表示一个导师是否已经被分配。如果第 j 位是 1，则表示导师 j 已经被分配；如果是 0，则表示还未被分配。
g[i][j]：表示学生 i 和导师 j 之间的兼容性评分。

初始化

f[0] = 0：表示没有导师被分配时，兼容性评分为 0。

状态转移

对于每一个状态 i（表示当前已经分配了某些导师），我们需要考虑将剩余未分配的导师分配给未分配的学生。

计算当前已经分配的导师数目 c：
- 使用 __builtin_popcount(i) 计算 i 中 1 的个数，即当前已经分配的导师数目。例如，如果 i 是 1010（二进制），那么 c 为 2，表示已经有 2 个导师被分配。
- 在升序枚举状态i时，c是递增的。
枚举每一位导师 j：
- 对于每一个可能的导师 j，检查 i 的第 j 位是否为 1。如果是 1，则表示导师 j 已经被分配，因此可以尝试分配给第c位学生，产生子问题。
- 如果 i 的第 j 位是 1，则尝试将导师 j 分配给当前的学生 c-1（因为 c 表示已经分配的导师数目，所以第 c 个学生对应的编号是c-1）。
更新 f[i]：
- 更新 f[i] 为 max(f[i], f[i ^ (1 << j)] + g[c-1][j])。
- 其中 i ^ (1 << j) 表示将 i 的第 j 位置为 0，即移除导师 j 的分配状态。
- g[c-1][j] 表示学生 c-1 和导师 j 之间的兼容性评分。
- 产生的子问题的最优解为f[i ^ (1 << j)]，子问题决策得到当前问题的影响是g[c-1][j]，因此当前问题的可能最优解为f[i ^ (1 << j)] + g[c-1][j]。

结果返回

最终答案就是 f[(1 << m) - 1]，即所有导师都被分配完时的最大兼容性评分和

代码实现

c++

class Solution {
public:
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int m=students.size(),n=students[0].size();
        vector<vector<int>>g(m,vector<int>(m)); // g[i][j]表示学生i和导师j的兼容性评分
        // 预处理g[i][j]
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<n;k++)
                    g[i][j]+=(students[i][k]==mentors[j][k]);
        vector<int>f((1<<m)); // f[i]表示导师分配状态为i时，得到的最大兼容性评分和
        for(int i=1;i<(1<<m);i++){
            int c=__builtin_popcount(i); // c表示数字i中1的数目，即当前状态已经分配的导师数目
            for(int j=0;j<m;j++){
                if(i&(1<<j)){ // 枚举，将当前状态i的一名导师j分配给第c位学生，取兼容性评分和最大的结果 
                    f[i]=max(f[i],f[i^(1<<j)]+g[c-1][j]);
                }
            }
        }
        return f[(1<<m)-1];
    }
};

状压DP ​

二进制位变换 ​

例题讲解 ​

公平分发饼干 ​

问题理解 ​

算法分析 ​

实现步骤 ​

初始化 ​

状态表示 ​

状态转移 ​

枚举所有可能的决策 ​

更新 DP 表 ​

优化空间复杂度 ​

代码实现 ​

最大兼容性评分和 ​

问题理解 ​

算法分析 ​

实现步骤 ​

预处理兼容性评分 ​

状态表示 ​

动态规划 ​

动态规划定义 ​

初始化 ​

状态转移 ​

结果返回 ​

代码实现 ​

状压DP

二进制位变换

例题讲解

公平分发饼干

问题理解

算法分析

实现步骤

初始化

状态表示

状态转移

枚举所有可能的决策

更新 DP 表

优化空间复杂度

代码实现

最大兼容性评分和

问题理解

算法分析

实现步骤

预处理兼容性评分

状态表示

动态规划

动态规划定义

初始化

状态转移

结果返回

代码实现