状态压缩dp,$O(M2^N2^N)$

#pragma GCC optimize(2)  //o2优化，此题可以把时间优化一倍
#include <iostream>
#include <cstring>
using namespace std;

const int N=12,M=(1<<11)+10;
bool st[M];  //表示每列2^11种状态是否存在连续奇数个0。false-是，true-否
long long f[N][M]; //f[i][j]表示第i列的第j种状态，共有f[i][j]中摆法

int main()
{
    int n,m;
    while(cin >> n >> m,n||m)  //直到读入的n和m都为0就退出循环
    {
        for(int i=0;i<1<<n;i++) //对st[]数组初始化,使得st[i]保存i状态是否存在连续奇数个0
        {
            st[i]=true;
            int cnt=0;  //记录i状态存在的连续0的个数
            for(int j=0;j<n;j++)  //枚举i的二进制数的每一位
            {
                if(i>>j&1)  //若i的第j位为1
                {
                    if(cnt&1)  //cnt&1==1表示cnt是奇数；cnt&1==0,表示cnt是偶数
                    {
                        st[i]=false;  //若cnt为奇数，即i状态出现了连续奇数个0
                        break;  //既然st[i]已经确定，则可以退出循环了（其实n最大也就11）
                    }
                }
                else cnt++;  //若i的第j位为0，则连续0的个数++
            }
            if(cnt&1) st[i]=false; //因为不存在第n行,需要特判最下面的几行连续0的情况
        }

        memset(f,0,sizeof f);  //对于每轮n,m.都要重新初始化f
        f[0][0]=1;  //第0列只有竖着摆这1种状态
        for(int i=1;i<=m;i++)  //从第1列开始，枚举每一列
            for(int j=0;j<1<<n;j++)  //枚举第i列的每一种状态
                for(int k=0;k<1<<n;k++)  //枚举第i-1列的每一种状态
                    if((j&k)==0 && st[j|k]) f[i][j]+=f[i-1][k];
        /*如果第i与i-1列的状态不存在占用冲突，且第i列不存在连续奇数个0,
          则f[i-1][k]是一种组成f[i][j]的合法方案*/
        cout << f[m][0] << endl; //第m-1列(即最后一列)不能有突出到m列的棋子,即第m的状态是0
    }
    return 0;
}

$O(M2^N*(合法状态数)）$ ,合法状态数远小于$2^N$

预选处理好每个j状态对应的所有合法的状态，并保存。此后f[i][j]计算时只需枚举所有合法状态相加

//#pragma GCC optimize(2)  //o2优化
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N=12,M=(1<<11)+10;
bool st[M];  //表示每列2^11种状态是否存在连续奇数个0。false-是，true-否
vector<vector<int>> validst(M);
long long f[N][M]; //f[i][j]表示第i列的第j种状态，共有f[i][j]中摆法

int main()
{
    int n,m;
    while(cin >> n >> m,n||m)  //直到读入的n和m都为0就退出循环
    {
        for(int i=0;i<1<<n;i++) //对st[]数组初始化,使得st[i]保存i状态是否存在连续奇数个0
        {
            st[i]=true;
            int cnt=0;  //记录i状态存在的连续0的个数
            for(int j=0;j<n;j++)  //枚举i的二进制数的每一位
            {
                if(i>>j&1)  //若i的第j位为1
                {
                    if(cnt&1)  //cnt&1==1表示cnt是奇数；cnt&1==0,表示cnt是偶数
                    {
                        st[i]=false;  //若cnt为奇数，即i状态出现了连续奇数个0
                        break;  //既然st[i]已经确定，则可以退出循环了（其实n最大也就11）
                    }
                }
                else cnt++;  //若i的第j位为0，则连续0的个数++
            }
            if(cnt&1) st[i]=false; //因为不存在第n行,需要特判最下面的几行连续0的情况
        }

        for(int j=0;j<1<<n;j++)  //预先处理2^n种j状态对应的合法状态，保存在二维数组中
        {
            validst[j].clear();   //清空上一轮不同n,m值遗留的状态
            for(int k=0;k<1<<n;k++)
                if((j&k)==0 && st[j|k]) validst[j].push_back(k); //保存合法状态，即相对于f[i][j]合法的的f[i-1][k]
        }

        memset(f,0,sizeof f);  //对于每轮n,m.都要重新初始化f
        f[0][0]=1;  //第0列只有竖着摆这1种状态
        for(int i=1;i<=m;i++)  //从第1列开始，枚举每一列
            for(int j=0;j<1<<n;j++)  //枚举第i列的每一种状态
                for(auto k :validst[j])  //枚举对于j状态的每一种 i-1列的合法状态
                    f[i][j]+=f[i-1][k];
        /*如果第i与i-1列的状态不存在占用冲突，且第i列不存在连续奇数个0,
          则f[i-1][k]是一种组成f[i][j]的合法方案*/
        cout << f[m][0] << endl; //第m-1列(即最后一列)不能有突出到m列的棋子,即第m的状态是0
    }
    return 0;
}