状态压缩DP

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];            // 第一维表示列， 第二维表示所有可能的状态，注意要用long long 否则会爆int
vector<int> state[M];
bool st[M];           //存储每种状态是否有奇数个连续的0,奇数为false，偶数为true
int main()
{
    while (cin >> n >> m, n || m)
    {
        //预处理1：利用连续未填格子的奇偶数去筛掉一些情况
        for (int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;        //记录连续的0的个数
            bool is_valid = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)       //如果是 i >> j == 1进入if
                {
                    if (cnt & 1)    //如果cnt是奇数
                    {
                        is_valid = false;
                        break;
                    }
                }
                else cnt ++ ;     
            if (cnt & 1) is_valid = false;    //判断最下面的那一段0的个数
            st[i] = is_valid;
        }
    //预处理2：看第i-2列伸出来的和第i-1列伸出去的是否冲突
        for (int i = 0; i < 1 << n; i ++ )    //对于第i列的所有情况
        {
            state[i].clear();                 //因为有多组输入，故每次操作要清空
            for (int j = 0; j < 1 << n; j ++ )//对于第i - 1列的所有情况
                if ((i & j) == 0 && st[i | j])// j|k 就是第 i-1 列的有几个1，即哪几行是横着放格子的
                    state[i].push_back(j);    //把合法的情况放入数组之中
        }
    //dp：
        memset(f, 0, sizeof f);    //多组输入数据，每次清空
        f[0][0] = 1;
        //按照定义，上一行中的代码指的是已经将前-1列摆好，且从-1列伸出到第0列的方案数为1   (类似空集)
        for (int i = 1; i <= m; i ++ )   //遍历每一列
            for (int j = 0; j < 1 << n; j ++ ) //遍历每一列的所有状态
                for (auto k : state[j])
                    f[i][j] += f[i - 1][k]; //当前列的方案数就等于之前的第 i-1 列所有状态k的和
        cout << f[m][0] << endl;
        //f[m][0]表示 前 m-1 列都处理完，并且第m-1列没有伸出来的所有方案数
    }
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;    //从0出发，经过的点集为1，即到达0这个点，即为0到0
    for (int i = 0; i < 1 << n; i ++ )  //开始枚举所有的情况
        for (int j = 0; j < n; j ++ )   //枚举到达的所有的点
            if (i >> j & 1)             //如果当前的点的集合包括点 j ，进行状态转移
                for (int k = 0; k < n; k ++ )   //枚举从哪一个点转移过来
                    if ((i - (1 << j)) >> k & 1) //去掉点 j 后，仍然包含 k
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1];   //最终输出 f[111...111][n - 1]
    return 0;
}