学习笔记：状压 DP

wsy_I · 2026-04-02 15:18:34 · 算法·理论

理论

在我们的 DP 转移中，可能会涉及到 DP 维数特别多，甚至和 n 挂钩的情况，但是每一个维数的状态都很少，一般为 2 个。

在这种情况下，我们可以不用开这么多维的 DP 数组，而是使用一个二进制数来表示这些维数，将这些维数压缩为一个二进制数的技巧就叫做状压，使用状压技巧的 DP 就被叫做状压 DP。由于二进制数的大小是呈指数级增长的，所以状压 DP 的数据范围一般不会太大。

状压 DP 一般处理的问题是下面三种：棋盘上状压，集合上状压，插头 DP。

1. 棋盘上状压

在棋盘上，我们会遇到很多选与不选的问题。在棋盘的某一行上，假设这一行的长度为 x，一共会有 2^x 种选择的方案。对于这 2^x 种选择的方案，我们没有必要使用 dp_{i_1,i_2,\ldots,i_x} 来存，而是使用一个二进制数，即 dp_{(i_1i_2\ldots i_x)_2}。

首先给出一道例题。

1.1 原理

我们首先分析这一道题的约束：

任意两头牛不能相邻。

拆开即为在纵向方面没有两头相连的奶牛，在横向方面也没有。因此，我们可以从这两个约束考虑设计状态。

首先，令 dp_{i,S} 为第 i 行，状态为 S 的方案数（这是一个很常见的状压 DP 状态设计），则答案显然为 \sum_{i} dp_{m,i}。接下来，考虑具体的如何状压以及转移。

1.1.1 状压方法

如前文所说，每一行的状态 S 可以具体表现为如下的情况：从左到右的每一格分别表示为 a_1,a_2,a_3,\ldots,a_n，其中 a_i 都是 0 或者 1，表示我们是否选择在这个方格放牛。我们可以将其表示为一个二进制数，具体可以使用以下的方法：

S=\sum^{n}_{i=0}2^ia_{i+1}

容易发现，这样得出来的所有 S 都没有重复。进一步推广，假如 a 的取值不只是 0,1，那么我们前面的底数可以增大，这样也可以保持状态没有重复。a 的取值不为 0,1 的情况，我们会在插头 DP 部分见到。

这样的话，S 的二进制下的第 i-1 位就是 a_i，这一个性质我们之后会反复使用。当然，为了状压编码方便，我们通常使用 0-based 数组，所以后文讨论的数组都是基于 0-based。

1.1.2 转移策略

首先，我们考虑一行中的合法状态。在一行中，状态合法必定满足下面的两个要求：

没有把牛放到贫瘠的土地上。具体的，我们可以使用一个 mp 数组来存储（这个数组的 mp_i 使用上面的方式状压），将 1 定义为草地，0 定义为贫瘠的土地。

因此，我们这一行合法即需要满足下面的这个表达式：((~mp[i]) & S) == 0，对于 mp 取反之后得到贫瘠的土地为 1，用按位与操作就可以判断是否有牛在贫瘠的土地上，如果没有牛（值为 0）就满足这个条件。
这一行没有相邻的两个奶牛。换言之，也就是这一行的奶牛假如全部向左移动一格，和之前的奶牛还是没有重合。（一个常见的转换）

因此，我们可以使用以下的位运算来完成这个判断：(S & (S << 1)) == 0。状压 DP 的编程中，一个很容易踩到的坑就是运算符优先级问题，所以建议没事多打点括号。

接下来，我们就可以考虑转移方程了。由于只需要状态合法就可以累加方案数，所以有一个显然的方程：

dp_{i,S}=\sum_{S_2}[\text{状态不冲突}]\times dp_{i-1,S_2}

其中的状态不冲突已经在之前讨论到了。

1.2 代码实现

1.2.1 一些常见操作

使用位运算可以方便的对于各种状压得到的东西进行操作。在下面列出一些常用的操作：

(S >> i) & 1：取第 i 位。
S & ((1 << i) - 1)：把 S 的第 i 位变为 0。
S ^ (1 << i)：把 S 的第 i 位变为 0，但是保证这一位之前是 1。比上一种更常用。
(S1 & S2) == 0：在 S_1 和 S_2 中没有相同部分。
!S：相当于 S == 0。
S：相当于 S != 0。
S ^ x：相当于 S != x。

1.2.2 例题代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 12 + 5;
const int M = (1 << 12) + 5;
const int MOD = 1e8;
int m, n, mp[N], dp[N][M], zt[M], k;

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> m >> n;
    for(int i = 0; i < m; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            int x;
            cin >> x;
            mp[i] ^= (x << j); //存储状态，这里的操作用^，|，+三种运算符均可。
        }
    }
    for(int i = 0; i < (1 << n); i ++)
        if(!(i & (i << 1))) zt[++ k] = i; //预处理全部合法状态
    for(int i = 1; i <= k; i ++)
        if(!((~mp[0]) & zt[i])) dp[0][i] = 1; //第一行初始值
    for(int i = 1; i < m; i++) //枚举当前行
        for(int j = 1; j <= k; j++) //枚举当前行状态
            for(int K = 1; K <= k; K++) //枚举上一行状态
                if(!((~mp[i]) & zt[j]) && //判断1：当前行合法
                !((~mp[i - 1]) & zt[K]) && //判断2：上一行合法
                !(zt[j] & zt[K])) //判断3：两行不冲突
                    dp[i][j] = (dp[i][j] + dp[i - 1][K]) % MOD;
    int ans = 0;
    for(int i = 1; i <= k; i++) ans = (ans + dp[m - 1][i]) % MOD; //统计答案
    cout << ans << endl;
    return 0;
}

1.3 例题

1.3.1 互不侵犯

link。

这一道题和前一道十分类似，只是国王使得不能四联通变成了不能八连通。因此，我们对于两行之间的合法判断要改一点：

第一种写法是 (S1 & S2) == 0 && (S1 & (S2 << 1)) == 0 && (S1 & (S2 >> 1)) == 0，这种写法很直观，就是下一行无论是左移还是右移还是不动都无法和上一行有相同点，但是有那么一点小长对不对。

所以有一种更加简洁的写法是这样的：(S1 & (S2 | (S2 << 1) | (S2 >> 1))) == 0，后面相当于先计算出下一行可以攻击到的上一行的格子，再看看有没有相同点。

由于需要记录国王的数量，所以我们的 DP 需要增加一维来记录数量。如何统计一个数的二进制下 1 的个数？C++ 提供了一个很好的函数：__bulitin_popcount(x)。

代码没有太多改动，就不放了。

1.3.2 炮兵阵地

link。

这一道题的约束要复杂一些，涉及到了两行，所以我们可以考虑将 DP 数组增加一维，定义 dp_{i,S_1,S_2} 为第 i 行，上一行状态为 S_1，这一行状态为 S_2 的最大可放炮兵数。

于是，我们转移的时候枚举上两行的方案，假如不冲突还是直接累加方案即可。不冲突共有以下约束（假设这一行状态为 S_1，上一行状态为 S_2，上两行状态为 S_3）：

上两行和上一行与这一行没有共同的位置有炮兵。可以写作 (S1 & (S2 | S3)) == 0。
这一行没有炮兵相邻或者隔着一个位置。可以写作 (S1 & ((S1 << 1) | (S1 << 2))) == 0。（隔着一个位置就是移了两位到这个位置）

代码如下：

#include <bits/stdc++.h>
#define endl '\n'
#define pcnt(x) __builtin_popcount(x)
using namespace std;

const int N = 100 + 5;
const int M = (1 << 10) + 5;
int dp[N][M][M];//dp_{i,j,k}：到i行，状态为j，上一行为k最多可以放几个
int n, m, mp[N], zt[M], tot;

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < m; j ++ )
        {
            char c;
            cin >> c;
            if(c == 'H') mp[i] += (1 << j);
        }
    }
    for(int S = 0; S < (1 << m); S ++ )
        if((S & ((S << 1) | (S << 2))) == 0)
            zt[tot ++ ] = S;
    for(int S1 = 0; S1 < tot; S1 ++ )
    {
        for(int S2 = 0; S2 < tot; S2 ++ )
        {
            if((mp[0] & zt[S1]) == 0)
                dp[0][S1][S2] = pcnt(zt[S1]);
            if(zt[S1] & zt[S2])
                continue;
            if((mp[0] & zt[S2]) == 0 && (mp[1] & zt[S1]) == 0)
                dp[1][S1][S2] = pcnt(zt[S1]) + pcnt(zt[S2]); 
        }
    }
    for(int i = 2; i < n; i ++ )
    {
        for(int S1 = 0; S1 < tot; S1 ++ )//这一行 
        {
            for(int S2 = 0; S2 < tot; S2 ++ )//上一行 
            {
                for(int S3 = 0; S3 < tot; S3 ++ )//上两行 
                {
                    if(zt[S1] & zt[S2] || zt[S1] & zt[S3])
                        continue;
                    if((zt[S1] & mp[i]) == 0 && (zt[S2] & mp[i - 1]) == 0 && (zt[S3] & mp[i - 2]) == 0)
                        dp[i][S1][S2] = max(dp[i][S1][S2], dp[i - 1][S2][S3] + pcnt(zt[S1]));
                }
            }
        }
    }
    int ans = 0;
    for(int S1 = 0; S1 < tot; S1 ++ )
        for(int S2 = 0; S2 < tot; S2 ++ )
            ans = max(ans, dp[n - 1][S1][S2]);
    cout << ans << endl;
    return 0;
}

1.3.3 国际象棋

link。

这一题要求我们求马的摆放方案数。由于这里是国际象棋没有撇马脚，所以这道题要方便很多。

首先，马的攻击还是会影响到上下两行的格子，所以我们考虑开两行来记录马这一行的摆放状态和上一行的摆放状态。然后，我们枚举三行的状态进行转移。

设这一行状态为 S_1，上一行状态为 S_2，上两行状态为 S_3，则判断可以写成这样：(S1 & ((S2 >> 2) | (S2 << 2) | (S3 >> 1) | (S3 << 1))) == 0。

代码改动也不多，就不放了。

1.3.4 蒙德里安的梦想

link。

这一道题和之前的棋盘状压有很大的区别，具体的区别在于这道题的 0/1 设计不是“放或者不放”，而是另一种方案。

首先先说一些基本的处理：交换矩阵的行列显然不影响答案，因此，我们可以让行的长度作为最小的那个数，这样状压 DP 由于主导项的指数和行长有关，会跑的快很多。然后，由于瓷砖的面积是 2，所以 m\times n 必须是偶数才有方案。

接下来，就到了设计 0/1 状态最关键的部分了。假如这一个骨牌是横着铺的，我们将这个骨牌的两个位置都置为 1，假如是竖着铺的，我们将上面的位置置为 0，将下面的位置置为 1。容易发现，这么设计状态一定能还原这个棋盘的摆放方案。

我们考虑两行之间，如何才是合法的转移。根据我们的定义，可以推出下面的几种约束：

假如上一行这一格是 0，这一行这一格必定是 1。
假如上一行这一格是 1，也有两种情况。
- 假如前一个格子是横着铺的第一个 1，那么当前格也必须是 1。
- 否则，当前格 0,1 均可。

这个判断比较复杂，可以选择逐位循环判断。

接着我们为了避免单独写第一行的初始化导致代码过长，我们可以考虑在第一行上面增添一个虚拟行，全为 1，这样不会漏掉任何合法的状态，也不会多算什么状态。

代码如下：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

bool judge(int k, int j, int cols)
{
    for(int i = 0; i < cols; )
    {
        if((k & (1 << i)) == 0) 
        {
            if((j & (1 << i)) == 0)
                return false;
            i ++;
        }
        else if((j & (1 << i)) != 0)
        {
            if(i == cols - 1 || (k & (1 << (i + 1))) == 0 || (j & (1 << (i + 1))) == 0)
                return false;
            i += 2;
        }
        else
            i ++;
    }
    return true;
}

const int N = 11 + 5;
const int M = (1 << 11) + 5;
int dp[N][M];

void solve(int h, int w)
{
    if((h * w) % 2 != 0)
    {
        cout << "0\n";
        return;
    }
    if(h < w) swap(h, w);
    memset(dp, 0, sizeof dp);
    int t = (1 << w) - 1;
    dp[0][t] = 1;
    for(int i = 1; i <= h; i ++ )
    {
        for(int j = 0; j <= t; j ++ )
        {
            for(int k = 0; k <= t; k ++ )
            {
                if(dp[i - 1][k] == 0) continue;
                if((k | j) == t && judge(k, j, w))
                    dp[i][j] += dp[i - 1][k];
            }
        }
    }
    cout << dp[h][t] << endl;
}

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int h, w;
    while(1)
    {
        cin >> h >> w;
        if(h == 0 && w == 0) break;
        solve(h, w);
    }
    return 0;
}

1.3.5 其它练习

01 矩阵
如果有什么另外的棋盘类状压的好题欢迎来补充。

2. 集合上状压

在集合问题中，我们也会有很多“元素选或不选”的情况。这种情况下，我们也可以将一个选择元素的状态压缩为一个二进制数，从而达到减少 DP 维数的效果。

这种问题的代表是 Hamilton 路（TSP）问题，除此之外还有一些其它的杂项。例题。

2.1 原理

状压的方法和棋盘类状压差不多，在这里不多讲。

首先，我们定义 dp_{i,S} 为以 i 结尾，经过了集合 S 的最短 Hamliton 路。为什么要这样定义？是为了 DP 的转移方便。假如直接定义 dp_{S} 为集合 S 的最短 Hamilton 路，那么我们会发现转移非常困难。

然后，转移方程就很好写啦~具体表现为

dp_{i, S}=\min dp_{j, S-i} + dis(j, i),i\in S,j\in S-i

也就是枚举以 i 结尾的 Hamilton 路的上一个节点是什么，然后取最小值即可。由于这里需要枚举 S,i,j，所以时间复杂度显然为 O(n^22^n)。

对于这里的集合 S-i，我们可以方便的使用 S ^ (1 << i) 得到，因为有 i\in S。

接着考虑初始值。由于是从 0 开始的，所以有 dp_{0,1} = 0，其它的 dp 值全都为 \infin。如果可以从任意节点开始，那么就有所有的 dp_{i,2^i}=0。

2.2 代码实现

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 25;
const int M = (1 << 20) + 10;
int dp[M][N], dis[N][N], n;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++) cin >> dis[i][j];
    }
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for(int S = 1; S < (1 << n); S++) //枚举S
    {
        for(int j = 0; j < n; j++) //枚举i
        { //判断：i ∈ S
            if(((S >> j) & 1)) for(int k = 0; k < n; k++) //枚举j
            {
                if(((S ^ (1 << j)) >> k) & 1) //判断：j ∈ S − i
                    dp[S][j] = min(dp[S][j], dp[S ^ (1 << j)][k] + dis[k][j]); //转移
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1]; //最后答案就是所有点，以 n - 1 结尾
    return 0;
}

2.3 例题

2.3.1 糖果

link。~~本文唯一黄题。~~

令 dp_S 为拿到状态为 S 的糖果所需要最少买多少包糖果。那么初始值显而易见：dp_0 = 0，其它的全为 \infin。

在这里，我们想要在枚举到某一个状态的时候从所有可以转移到这个状态的状态转移过来的话（这句话可能会有点绕），那么可能的状态非常多，并不好做，我们考虑正难则反，使用一个状态的当前值取更新它可以转移到的所有状态。方程如下，其中 c 表示每一包糖果的状压值：

dp_{S\vert c_i}=\min(dp_{S\vert c_i}, dp_S + 1)

注意题目里面的一包糖果对于每一种可能不止一颗，所以要使用 |= 来更新。

这道题过于简单，就不放代码了。

2.3.2 单词游戏

link。

这道题看着不是 Hamilton 路，其实就是 Hamilton 路。定义 dp_{S,i} 为状态 S，以 i 结尾的单词所能够拼出来的最长长度。接着考虑转移。

我们可以枚举一个状态的结尾单词，然后再枚举这个结尾单词从哪里转移过来。然后我们就会发现，这个转移方程长得出奇的像 Hamilton 路（其中 len 表示每个字符串的长度）：

dp_{S,i} = \min dp_{S-i,j} + len_i, i\in S, j\in S-i

注意这一道题并不需要我们将这些单词拼完，所以我们需要枚举所有状态取一个最大值。

代码太像 Hamilton 路了，就不放了。

2.3.3 愤怒的小鸟

link。

首先我们考虑抛物线具体该如何处理。容易发现一条优秀的抛物线至少砸死两只小猪，那我们就可以枚举两只小猪来算出所有可能的抛物线，并且将其视作一种转移方案。假设两个点分别为 (x_1,y_1) 和 (x_2,y_2)，那么过原点和这两个点的抛物线解析式就是 y=\dfrac{x_2y_1-x_1y_2}{x_1x_2(x_1-x_2)}x^2+\dfrac{x^2_2y_1-x^2_1y_2}{x_1x^2_2-x^2_1x_2}x。（消元可得）

注意在所有的抛物线以外，可能有些小猪和其它的小猪无法形成抛物线，所以我们在每次转移的时候特殊考虑使用一条抛物线打掉一只小猪。

然后接下来的分析就和糖果本质相同了。我感觉这道题有蓝纯属是因为代码难写。

#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;

const double eps = 1e-8;
const int N = 18 + 5;
const int M = (1 << 18) + 5; 
int T, n, m, tot, dp[M], pw[N * N];
double x[N], y[N], pwx[N * N], pwy[N * N];

inline bool eql(double a, double b) { return fabs(a - b) <= eps; }
inline bool le(double a, double b) { return a - b <= eps;  }
inline bool ge(double a, double b) { return b - a <= eps; }
inline bool les(double a, double b) { return a - b <= -eps; }
inline bool grt(double a, double b) { return b - a <= -eps; }

pair<double, double> get(int i, int j) //算抛物线
{
    pair<double, double> ans;
    ans.fi = (x[j] * y[i] - x[i] * y[j]) /
             (x[i] * x[j] * (x[i] - x[j]));
    ans.se = (x[j] * x[j] * y[i] - x[i] * x[i] * y[j]) /
             (x[i] * x[j] * x[j] - x[i] * x[i] * x[j]);
    return ans;
}

void solve()
{
    tot = 0;
    for(int i = 0; i < N * N; i ++)
        pwx[i] = pwy[i] = pw[i] = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> x[i] >> y[i];
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i + 1; j <= n; j ++) //暴力去重
        {
            if(eql(x[i], x[j])) continue;
            auto [a, b] = get(i, j);
            if(ge(a, 0)) continue;
            bool nw = true;
            for(int k = 0; k < tot; k ++)
                if(eql(a, pwx[k]) && eql(b, pwy[k])) nw = false;
            if(nw)
                pwx[tot] = a, pwy[tot] = b, tot ++;
        }
    }
    for(int i = 0; i < tot; i ++) 
    {
        for(int j = 1; j <= n; j ++)
            if(eql(pwx[i] * x[j] * x[j] + pwy[i] * x[j], y[j]))
                pw[i] |= (1 << (j - 1));
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for(int S = 0; S < (1 << n); S ++) //我就说本质相同吧，方程都是一样的
    {
        for(int i = 0; i < tot; i ++)
            dp[S | pw[i]] = min(dp[S | pw[i]], dp[S] + 1);
        for(int i = 0; i < n; i ++) //特殊考虑打掉一只猪的情况
            dp[S | (1 << i)] = min(dp[S | (1 << i)], dp[S] + 1);
    }
    cout << dp[(1 << n) - 1] << endl;
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T --)
        solve();
    return 0;
}

2.3.4 宝藏

link。

一道很好的题。这个问题是在无向图上求一个生成树，但是这道题由于性质很特殊，所以最小生成树算法都挂掉了，我们考虑状压 DP。其实这道题可以记搜。

首先，我们的树需要一个根才能算深度，所以我们枚举每一个节点为根跑记搜。在单次记搜中，定义 dp_{u,d,S} 表示来到节点 u，其深度为 d，并且以这个节点为根的子树中含有 S 的节点。于是呢，我们可以进行以下的转移：

对于 u 节点，枚举它的每一个邻接节点，设这个邻接节点为 v。于是，我们可以枚举子集，将 v 节点的子树的状态设定为这个子集。（设为 S_2）于是我们将这个大问题 dp_{u,d,S} 拆分为两个小问题：dp_{v,d+1,S_2} 和 dp_{u,d,S-S_2}。由于这里有 S_2\in S，所以我们可以用 S ^ S2 方便的得到 S-S_2。

于是我们就可以写出一个很朴素的记搜了。但是呢，假如你的实现不够优秀，就很容易爆 TLE。所以有下面的一些卡常技巧：

枚举子集的时候从 S-u 中枚举子集而不是从 S 中，这样会快一倍。
使用临接矩阵存储而不是 vector。STL 常数大，这道题图非常稠密。
使用一个中间变量存储 S-u，这样会避免每次计算的开销。
使用一个引用记录 dp_{u,d,S}，这样访问会快一点，原理我也不是很清楚。
函数前面加 inline 会有一些神奇的编译器优化，虽然要注意不要让编译器给你负优化。

具体代码实现如下：

#include <bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;

const int N = 12 + 5;
const int M = (1 << 12) + 5;
const int INF = 0x3f3f3f3f;
int n, m, dp[N][N][M], ans = INF, mp[N][N];

inline int dfs(int u, int d, int S)
{
    int &res = dp[u][d][S];
    if(res != INF) return res;
    if(S == 0) return res = 0;
    int x = INF;
    for(int v = 1; v <= n; v++)
    {
        if((S >> (v - 1)) & 1)
        {
            int w = mp[u][v];
            if(w != INF)
            {
                int rest = S ^ (1 << (v - 1));
                for(int T = rest; ; T = (T - 1) & rest)
                {
                    int val = dfs(v, d + 1, T) + dfs(u, d, rest ^ T) + d * w;
                    if(val < x) x = val;
                    if(T == 0) break;
                }
            }
        }
    }
    return res = x;
}

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    memset(mp, 0x3f, sizeof mp);
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if(w < mp[u][v])
        {
            mp[u][v] = w;
            mp[v][u] = w;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        memset(dp, 0x3f, sizeof dp);
        int f = (1 << n) - 1;
        int S = f ^ (1 << (i - 1));
        ans = min(ans, dfs(i, 1, S));
    }
    cout << ans;
    return 0;
}

2.3.5 其它练习

吃奶酪
补给
售货员的难题
路段最
灰化肥，会挥发
Cows in a skyscraper
如果有其它集合上状压的好题可以找我添加。

3. 插头 DP

这是一个比较困难的东西，是 CDQ 大人在 2008 年发明的，可以解决棋盘上的很多问题，例如闭合回路计数。虽然这种 DP 也是在棋盘上的，但是区别是棋盘上状压是逐行转移，插头 DP 是逐格转移。

题目。 ::::info[样例解释 #1] ::::

3.1. 原理

3.1.1 定义

插头 DP：一种状压 DP。因此，它的时间复杂度通常不低，数据范围通常较小（例题里表现为 n,m\le 12）。
当前决策点：插头 DP 目前在转移的点。
轮廓线：一条分割未转移节点和已转移节点的折线。
插头：一个已决策格子连向未决策格子，要求必须满足能够形成闭合回路之类的性质。一个格子最多有两个插头。
联通分量：通过已决策格子形成的联通块。

如果不太理解上面的那些东西，我们可以画个图：

深蓝色线条是目前决策出来的线，蓝色方格是当前决策点，红色折线是轮廓线，深红色箭头是插头。在上图中，已决策格子形成一个大的联通分量。

容易发现插头 DP 是逐格转移的。因此，我们定义 dp_{i, j, S} 为格子 (i, j)，轮廓线状态为 S 的时候的方案数。

3.1.2 状压方式：括号表示法

在方格的闭合回路上，假如插头 a, b, c, d 按照从左到右的顺序，那么有以下性质：假如插头 a, c 通过已决策节点相连，那么 b, d 必定不会通过已决策节点相连。可以理解为插头 b 被插头 a, c 之间连接的方案给挡住了，所以连不到 d。

这种不能交叉的匹配方案，我们容易想到括号匹配。因此，我们可以使用括号序列来表示一个状态，其中使用 () 来表示一堆相互联通的插头，使用 * 来表示当前格子没有插头。上面的例子中，我们将其表示为 (***)**，写成三进制就是 (0222122)_3，但是我们可以使用四进制，这样可以用位运算，会快一些。

接下来，我们复习一下状压 DP 的操作（可以跳过，使用四进制方法）：

::::info[复习时间！]

(S >> (x << 1)) & 3：取第 x 位，由于是四进制所以移位的位数要乘以 2，最后取的是后两位。
S ^ (((S >> (x << 1)) & 3) << (x << 1)) 把 S 的第 x 位置为 0。 ::::

3.1.3 转移

有这么几种情况，分类讨论。

第一种情况：当前决策点的上下均没有插头。

那么当前决策点就只能新开一个联通分量了，当前格会获得向右的插头和向下的插头。

在括号表示法中，具体表现为以下：

之前的轮廓线是 (***)，现在的新轮廓线是 (()*)。容易发现就是把相邻的两个插头状态从无插头变成了互相匹配。

第二种情况：当前决策点只有下插头或者右插头。

那么我们当前节点首先肯定需要保持上方联通，接着下一个插头往右边插还是往下边插均可。（虽然上面的图是边缘所以只能往下边插）

之前的轮廓线是 (()*)，更新之后轮廓线变为 *(())。

由于这里换行了，所以上面原本的轮廓线后移了一位。这里涉及到的轮廓线变换较多，具体实现可以考虑拆位之后统一修改。但是，假如不换行，就是直接将当前节点的插头更新一下。（是左括号还是右括号继承之前的插头，如果方向改变就修改一下，否则轮廓线不变）

第三种情况：当前决策点有下插头也有右插头。

当前决策点必须要和指向他的插头接上，所以当前节点不能有下插头和右插头。

考虑轮廓线的变化，之前的轮廓线是 *(())，变成了 ***()。容易发现是把一对插头变成了没有插头的状态，然后修改了另外一对插头的配对，因为另外的这一对插头已经联通了。

2. 代码实现

3.2.1 一些细节

注意到这里是一个很经典的统计方案的 DP，直接从转移过来的状态累加即可。

然后，假如你代码写的比较丑，没有用滚动数组，直接定义 dp_{i,j,S} 的话，你可能会~~高兴的~~爆 MLE，发现 i, j 都可以被滚动数组优化掉，因此 0/1 滚动一下即可。

接着，有一个小优化就是这样的：注意到我们使用了四进制，所以有很多状态都是无用的，瞎枚举肯定不优秀，用哈希表存储下一个格子有用的状态可以大大优化。手写哈希肯定要比 unordered_map 或者 gp/cc_hash_table 的常数要好很多，下面的代码使用挂表法实现。

知道了上面这些知识，我们就可以愉快的写代码啦~具体问题看代码注释吧。

3.2.2 完整实现

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 20 + 5;
const int K = 3e5 + 5;
int n, m, endx, endy;
char pl[N][N];
int state[2][K], tot[2], d, f[2][K], ans;

namespace Hash //哈希表 
{
    const int HASH_MOD = 257483; //随便打的 
    struct hash_table
    {
        int head[K], nxt[K];
        void insert(int x, int s)
        {
            int p = x % HASH_MOD + 1, u = head[p];
            while(u)
            {
                if(state[d][u] == x)
                {
                    f[d][u] += s;
                    return;
                }
                u = nxt[u];
            }
            nxt[ ++ tot[d]] = head[p];
            head[p] = tot[d];
            state[d][tot[d]] = x;
            f[d][tot[d]] = s;
        }
        void clear()
        {
            memset(head, 0, sizeof head);
            tot[d] = 0;
        }
    };
}

Hash :: hash_table hsh;
int bin[N], a[N][N];

int DP()
{
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= tot[d]; j ++ ) //处理两行之间轮廓线的转移 
            state[d][j] <<= 2;
        for(int j = 1; j <= m; j ++ )
        {
            d ^= 1;
            hsh.clear();
            for(int k = 1; k <= tot[d ^ 1]; k ++ )
            {
                int now_state = state[d ^ 1][k];
                int p1 = (now_state >> ((j - 1) << 1)) & 3; //插头1 
                int p2 = (now_state >> (j << 1)) & 3; //插头2 
                int s = f[d ^ 1][k]; //当前格子 DP 值 
                if(!a[i][j]) //case 1: 格子是障碍 
                {
                    if(!p1 && !p2)
                        hsh.insert(now_state, s); //直接继承当前状态 
                }
                else if(!p1 && !p2) //case 2: 格子没有插头 
                {
                    if(a[i][j + 1] && a[i + 1][j])
                        hsh.insert(now_state + 2 * bin[j] + bin[j - 1], s); //向两边各插一个插头 
                }
                else if(!p1 && p2) //case 3: 只有插头 2
                {
                    if(a[i][j + 1])
                        hsh.insert(now_state, s); //插头同向 
                    if(a[i + 1][j])
                        hsh.insert(now_state - bin[j] * p2 + bin[j - 1] * p2, s); //插头不同向 
                }
                else if(p1 && !p2) //case 4: 只有插头 1 
                {
                    if(a[i][j + 1])
                        hsh.insert(now_state - bin[j - 1] * p1 + bin[j] * p1, s);
                    if(a[i + 1][j])
                        hsh.insert(now_state, s); //这几行和上面大致相同 
                }
                else if(p1 == 1 && p2 == 1) //case 5: 两个插头，且都是左括号
                {
                    int rc = 1;
                    for(int l = j + 1; l <= m; l ++ ) //找后一个和这个插头匹配的插头 
                    {
                        if(((now_state >> (l << 1)) & 3) == 1) rc ++;
                        if(((now_state >> (l << 1)) & 3) == 2) rc --;
                        if(!rc) //找到了，抹掉这两个插头，改变另一个插头的配对 
                        {
                            hsh.insert(now_state - bin[j] - bin[j - 1] - bin[l], s);
                            break;
                        }
                    }
                }
                else if(p1 == 2 && p2 == 2) //case 6: 两个插头，且都是右括号
                {
                    int lc = 1;
                    for(int l = j - 2; l >= 0; l -- ) //和上面大致相同 
                    {
                        if(((now_state >> (l << 1)) & 3) == 2) lc ++;
                        if(((now_state >> (l << 1)) & 3) == 1) lc --;
                        if(!lc)
                        {
                            hsh.insert(now_state - 2 * bin[j] - 2 * bin[j - 1] + bin[l], s);
                            break;
                        }
                    } 
                }
                else if(p1 == 2 && p2 == 1) //case 7: 两个插头配对不同
                    hsh.insert(now_state - 2 * bin[j - 1] - bin[j], s); //直接抹掉两个插头 
                else if(i == endx && j == endy) //case 8: 到终点了，统计答案 
                    ans += s; 
            }
        }
    }
    return ans;
}

signed main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m; j ++ )
        {
            cin >> pl[i][j];
            a[i][j] = (pl[i][j] == '.'); 
            if(pl[i][j] == '.')
                endx = i, endy = j;
        }
    }
    bin[0] = 1;
    for(int i = 1; i <= 12; i ++ )
        bin[i] = bin[i - 1] << 2;
    tot[d] = f[d][1] = 1;
    state[d][1] = 0;
    cout << DP() << endl;
    return 0;
}

参考资料

浅谈状压DP
浅谈状压 DP
题解 P5056 【【模板】插头dp】
题解 P5056