这种动归有很多名字，插头DP是最常见的
还有基于连通性的动态规划
轮廓线动态规划等等
超小数据范围，网格图，连通性
可能算是状态压缩DP的一种变式
以前我了解的状压DP用于NP难题的小数据范围求解
这里说一下哈密顿回路的概念：
哈密顿回路：
、指一个对图的每个顶点都只穿越一次的回路。也可以 定义为n+1个相邻顶点v0, v1, … ,vn, v0的一个序列，其中序列的第一个顶点和最后一个顶点是相同的，而其他n-1个顶点是互不相同的。
、当这个图是加权图时，求该图的最短哈密顿回路，就是传说中的旅行商问题（TSP）。
然后是一道插头DP的入门题
一个网格图中有若干障碍格子，求其他格子的哈密尔顿回路总数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int LIM=,Has=;
int n,m,e1,e2,las,now,tt;LL ans;
int mp[][],bin[],tot[];LL js[][LIM];
int h[],a[][LIM],ne[LIM];
//tot:状态总数,js:该状态的方案总数,a:各种状态
void ins(int zt,LL num) {//卓越的哈希技术
int tmp=zt%Has+;
for(int i=h[tmp];i;i=ne[i])
if(a[now][i]==zt) {js[now][i]+=num;return;}
ne[++tot[now]]=h[tmp],h[tmp]=tot[now];
a[now][tot[now]]=zt,js[now][tot[now]]=num;
}
void work() {
tot[now]=,js[now][]=,a[now][]=;
for(int i=;i<=n;++i) {
for(int j=;j<=tot[now];++j) a[now][j]<<=;//切换行了
for(int j=;j<=m;++j) {
las=now,now^=;
memset(h,,sizeof(h)),tot[now]=;
for(int k=;k<=tot[las];++k) {
int zt=a[las][k],b1=(zt>>(j*-))%,b2=(zt>>(j*))%;//提取关键格子上的两段轮廓线状态
LL num=js[las][k];
if(!mp[i][j]) {if(!b1&&!b2) ins(zt,num);}
else if(!b1&&!b2)
{if(mp[i+][j]&&mp[i][j+]) ins(zt+bin[j-]+*bin[j],num);}
else if(!b1&&b2) {
if(mp[i][j+]) ins(zt,num);
if(mp[i+][j]) ins(zt-bin[j]*b2+bin[j-]*b2,num);
}
else if(b1&&!b2) {
if(mp[i][j+]) ins(zt-bin[j-]*b1+bin[j]*b1,num);
if(mp[i+][j]) ins(zt,num);
}
else if(b1==&&b2==) {
int kl=;
for(int t=j+;t<=m;++t) {
if((zt>>(t*))%==) ++kl;
if((zt>>(t*))%==) --kl;
if(!kl) {ins(zt-bin[j]-bin[j-]-bin[t],num);break;}
}
}
else if(b1==&&b2==) {
int kl=;
for(int t=j-;t>=;--t) {
if((zt>>(t*))%==) --kl;
if((zt>>(t*))%==) ++kl;
if(!kl) {ins(zt+bin[t]-*bin[j]-*bin[j-],num);break;}
}
}
else if(b1==&&b2==) ins(zt-*bin[j-]-bin[j],num);
else if(i==e1&&j==e2) ans+=num;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j) {
char ch=getchar();
while(ch!='*'&&ch!='.') ch=getchar();
if(ch=='.') mp[i][j]=,e1=i,e2=j;
}
bin[]=;for(int i=;i<=;++i) bin[i]=bin[i-]<<;
work(),printf("%lld\n",ans);
return ;
}
然后是HDU1693
给一个n*m的地图，有些格子是不可到达的，要把所有可到达的格子的树都吃完，并且要走回路，求方案数
允许有多个回路，找一条或多条回路，吃完所有的树
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,T,kas,bin[],mp[][];LL f[][][(<<)];
int main()
{
scanf("%d",&T);
bin[]=;for(int i=;i<=;++i) bin[i]=bin[i-]<<;
while(T--) {
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j) scanf("%d",&mp[i][j]);
memset(f,,sizeof(f));
f[][m][]=;int lim=bin[m+]-;
for(int i=;i<=n;++i) {
for(int zt=;zt<=lim;++zt) f[i][][zt<<]=f[i-][m][zt];
for(int j=;j<=m;++j)
for(int zt=;zt<=lim;++zt) {
int b1=zt&bin[j-],b2=zt&bin[j];LL num=f[i][j-][zt];
if(!mp[i][j]) {if(!b1&&!b2) f[i][j][zt]+=num;}
else if(!b1&&!b2)
{if(mp[i][j+]&&mp[i+][j])f[i][j][zt+bin[j-]+bin[j]]+=num;}
else if(!b1&&b2) {
if(mp[i][j+]) f[i][j][zt]+=num;
if(mp[i+][j]) f[i][j][zt-bin[j]+bin[j-]]+=num;
}
else if(b1&&!b2) {
if(mp[i][j+]) f[i][j][zt-bin[j-]+bin[j]]+=num;
if(mp[i+][j]) f[i][j][zt]+=num;
}
else f[i][j][zt-bin[j-]-bin[j]]+=num;
}
}
printf("Case %d: There are %lld ways to eat the trees.\n",++kas,f[n][m][]);
}
return ;
}