状压dp
详细注释,具体的思路都写到代码注释里了,这个代码没有用滚动数组,就是普通的dp,但是思路很清晰,很详细,希望对大家有帮助
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1e7+10,mod=1000000007;
//对于g数组的解释:
//首先一列有四种状态,将格子有方块表示为1,无方块表示为0,则一列的状态可以表示为00,01,10,11
//所以我们可以得到每一列具体的状态
//之后,为了表示每一种状态之间的转换关系,我们设置了g数组,其中元素的意义是:
//g[x][y)表示第x种状态是否可以转换为第y种状态,如果可以,g[x][y]=1,否则g[x][y]=0
//至于状态的转换的说明:当i-1列为11时,因为第i-1列无法再放置方块,所以第i列只有00这一种状态
// 当i-1列为01时,i列可以是11,10;
// 当i-1列为10时,i列可以是11,01;
// 当i-1列为00时,i列可以是00,01,10,11这四种状态;
//说明:例如g[1][3]表示第01种状态是否可以转换为11状态,如果为1就表示可以转化,反之不能
int g[4][4]={
{1,1,1,1},
{0,0,1,1},
{0,1,0,1},
{1,0,0,0}
};
int n;
cin>>n;
//我们下标从1开始,也就是1-n不是0-(n-1)
//f[1][0]从定义出发,表示前0列都填满的情况下,第1列的状态只能为00,因为第1列是首列,不可能被前面的
//列给填上某一个格子
//所以f[1][0]的总方案数只能是1;
f[1][0]=1;
//从第二列开始
for(int i=2;i<=n+1;i++)
{
//遍历第i列的4种状态
for(int j=0;j<4;j++)
{
//遍历第i-1列的4种状态
for(int k=0;k<4;k++)
{
//对于f[i-1][k]*g[k][j]的理解:
//遍历第i-1列的四种状态,用k来表示,因为当前第i列的状态为j,所以通过g数组判断
//状态j是否可以转化为状态k,g[k][j]为1就表示可以,反之就表示不行;
//如果可以的话就在f[i][j]的基础上加上f[i-1][k]的方案数,因为g数组中存的就是0和1,所以
//不用单另判断k是否可以转化为j
f[i][j]=(f[i][j]+f[i-1][k]*g[k][j])%mod;
}
}
}
//f[n+1][0]表示前N列已经填满,并且第n+1列没有格子伸过来,也就是n+1列是空的
cout<<f[n+1][0];
return 0;
}