状态压缩dp，常见的套路就是一行一行放，或者一列一列放，如果没有其他的要求的话，那么状态表示就是二维的，
但一般有其他维度的限制，这里举二维为例，
f[i,j]表示已经放好了前i-1行(列)，并且第i行(列)
的状态是j，这是最朴素的写法，首先想好每一列或者每一行合法的状态，再思考相邻两列或者两行的状态是否兼容，也就是
能不能进行合法的状态转移，这一步其实优化后的状压dp也需要做这一步，但仔细一想，在枚举中有很多无意义的状态，显然，
可以采用一种预处理的思路，来对状压dp进行优化，预处理出所有合法状态，再预处理出所有的合法状态转移，
这样不仅优化了无效状态，还使状态转移可以用查表的方式，
效率得到了极大的提升，AcWing 1064 小国王，很难找到一份带朴素版的题解，
在这里贴上朴素版和优化版的代码

朴素版小国王代码,朴素版会超时，11个数据过7个

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int N=20;
int n,k;  //n*n的棋盘，k个国王
LL f[N][1<<10][110];
//的所有方案
bool check(int x){
    for(int i=1;i<n;i++){
        if((x>>i&1)&&(x>>(i-1)&1))return false;
    }
    return true;
}
int checksum(int x){
    int cnt=0;
    while(x){
        if(x&1)cnt++;
        x=x>>1;
    }
    return cnt;
}
int main(){
    scanf("%d%d",&n,&k);
    //考虑边界
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=1<<n;j++){
            for(int q=0;q<=k;q++){
                if(check(j)){
                //不合法的方案统一处理为0
                int t=checksum(j);
                if(q>=t){
                    //枚举所有的合法转移方案
                    for(int a=0;a<1<<n;a++){
                        if(check(a)&&(a&j)==0&&check(a|j))f[i][j][q]+=f[i-1][a][q-t];
                    }
                }
                }
            }
        }
    }
    LL ans=0;
    //最后扫描最后一行，把所有的方案获取过来
    for(int i=0;i<1<<n;i++)ans+=f[n][i][k];
    cout<<ans;
    return 0;
}

再贴一个预处理优化版的,解题思路都在注释中

//闫氏dp思考法：动态规划问题首先考虑状态表示，本题有三维，假设f[i][j][k]分别表示对应
//前i行已经放完了，第i行的合法状态下标是j，国王的数量是k的一个摆放方法,对应的属性是
//方案数，方案数一般就对第0列置为1，什么都不做也是一种方案，然后说一下为什么是
//对应的下标，这是状态压缩dp的一种优化，把状态转移变成了下标的一种映射关系，还有每个
//下标对应的国王数必须小于等于枚举的国王数才能进行转移，要不然不合法
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
const int N=20;
int n,k;  //n*n的棋盘，k个国王
LL f[N][1<<10][110];  //表示前i行已经放好了，下标为j的合法状态，已经放了k个国王
vector<int>sum;  //存储一行的所有合法状态
vector<int>head[1<<10];
//的所有方案
bool check(int x){
    for(int i=1;i<n;i++){
        if((x>>i&1)&&(x>>(i-1)&1))return false;
    }
    return true;
}
int checksum(int x){
    int cnt=0;
    while(x){
        if(x&1)cnt++;
        x=x>>1;
    }
    return cnt;
}
int main(){
    scanf("%d%d",&n,&k);
    //首先处理一行所有的合法状态
    for(int i=0;i<1<<n;i++){
        if(check(i))sum.push_back(i);
    }
    //然后处理合法的状态转移
    for(int i=0;i<sum.size();i++){
        for(int j=0;j<sum.size();j++){
            int a=sum[i],b=sum[j];
            if(((a&b)==0)&&check(a|b))head[i].push_back(j);
        }
    }
    //考虑边界
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<sum.size();j++){
            for(int q=0;q<=k;q++){
                //不合法的方案统一处理为0
                int t=checksum(sum[j]);
                if(q>=t){
                    //枚举所有的合法转移方案
                    for(int a=0;a<head[j].size();a++){
                        f[i][j][q]+=f[i-1][head[j][a]][q-t];
                    }
                }
            }
        }
    }
    LL ans=0;
    //最后扫描最后一行，把所有的方案获取过来
    for(int i=0;i<sum.size();i++)ans+=f[n][i][k];
    cout<<ans;
    return 0;
}