状态压缩

用整数表示一个状态（二进制数），维护一个二维数组表示问题

方格划分

原题：291. 蒙德里安的梦想 - AcWing题库

将给定长宽的矩形分割为 1x2 的多个长方形，问有多少方案数

状态表示

当分割到当前列时，当前的分割法方案的总和

用当前列，与当前列在分割后的下一列状态的二进制表示（0 1 表示有无方块）来表示状态

状态计算

考虑到只要横向填好了，竖向也确定了 以横向分类：

• 以当前列与前一列的相容（不冲突）的下一列状态（当前这一列填完后延申到下一列的状态）二进制表示来分类
• 就是说在不同的方案组合下，每一列的下一列会有变化，考虑不同的前一列方案与这一列方案来求和得到最多的可能方案。

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 12, M = 1 << N;
 
 
long long f[N][M];
bool st[M];
 
int main()
{
    // 全局做一遍，初始化st，奇数0就返回错值
    for(int i = 0; i < 1 << N; i ++)
    {
        int cnt = 0;
        st[i] = true;  //全局初始化为false，这里让每个变为true，只有奇数0才变false
        
        for(int j = 0; j < N; j ++)
        {
            //遍历每一位
            if(i >> j & 1)
            {
                // 找到1，说明这之前的0统计完了
                // 有奇数0，就赋值false
                if(cnt  & 1)  st[i] = false;
                cnt = 0;
            }
            else cnt ++; //统计0的个数
        }
        
        //避免漏了最后一次
        if(cnt & 1) st[i] = false; 
    }
    
    
    int n, m;
    
    //新形式
    while(cin >> n >> m, n || m)
    {
        //每次查询都要初始化一下数组
        memset(f, 0, sizeof f);
        
        
        // 第0列只有竖着放这一种方案
        f[0][0] = 1;
        
        /*dp
         j， k是整数表示二进制数，所以从0遍历到2^n次，如果有出现状态冲突
        或者奇数个0，状态不能转移
        f[i][j] 表示到第i列时，j这种状态下的最大可能方案*/
        for(int i = 1; i <= m; i ++)
            for(int j = 0; j < 1 << n; j ++)
                for(int k = 0; k < 1 << n; k ++)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i-1][k];
                        
        
        //最后一列的下一列状态应该是0
        cout << f[m][0] << endl;
    }
    
    return 0;
}

最短Hamilton路径

从0 到 n-1 ，每个点都恰好经过一次

状态表示

利用二进制数对题目中可能的状态进行压缩，此题对某个时刻经过的点的状态进行压缩表示

集合为当经过 j 这个点的时候，已经走过 i 这个状态表示的点了

属性：MIN

状态计算

对前一个状态做分类： 当前到 j 点，前一个状态可以是0~k 点

当前的路径长度可以表示为 f[i][j] = f[i - {j}][k] + a[k][j] 前一个 i 中没有经过 j 的状态 加上 k 到 j 的距离

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 21, M = 1 << N;
 
int a[N][N];
int f[M][N];
 
int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
            cin >> a[i][j];
    }
    
    // 因为取最小
    memset(f, 0x3f, sizeof f);
    
    //赋初值，起点只经过自己，路径为0
    f[1][0] = 0;
    
    //dp
    for(int i = 0; i < 1 << n; i ++)
        for(int j = 0; j < n; j ++)
            //走到了j
            if(i >> j & 1)
            {
                for(int k = 0; k < n; k ++)
                // 去到j之前去到了k
                    if((i - (1 << j)) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);
            }
            
    int ans = f[(1 << n) - 1][n - 1];
    
    cout << ans << endl;
    
    return 0;
}

状态压缩有两个重要的点：

• 二进制状态表示 对状态进行的二进制表示，利用二维数组对于图，矩阵一类可以做到表示出所有状态，一般表示为当前的位置与当前的状态
• 初值的确定 dp问题实际上是递归问题，初值或许可以理解成终止条件，是一定要考虑的，需要给定的。