题目大意：有两种积木块，I型和L型，给定一段2*N的画布，问摆满总共有多少种方式？
解法：状态压缩dp（强烈建议拿个笔跟着画一下状态，慢慢就懂了）
首先我们规定一下此题解中提到的状态：
在第i列中会有两格（因为2*N），0表示未被占，1表示被占了，即如果两个格子都未被占则表示00，上面的未被占，下面的被占了表示01；同理10表示上面被占，下面未被占，11表示全都被占
另外，一旦发生状态转移，那么一定会让当前的列被占满！（为了防止重复情况，所以需要规定当前列占满，也可以规定下一列占满），这里看不懂先跳过，后面就看懂了
解题思路：
1.定义状态数组f[i][j]：i表示当前的位置，j表示当前位置的状态，f[i][j]表示在前i-1已经摆满的前提下总共有多少中摆放方式
2.构建转移数组g[j][k]：j表示转移前的状态，也就是当前（第i列）状态；k表示转移后i+1列的状态
（1）对于转移前第i列会有四种状态即00，01，10，11（再次强调i-1列已经满了，第i列可能被占是因为放i-1列的时候“不小心”占用了它，这也是为什么上面要规定发生状态转移，当前列被占满）
（2）前提：一旦发生状态转移就要填满第i列！那么如果当前列为00，我们便有四种摆放方式把它填满，自己动手画一下，加深理解！四种方式摆放完对应的i+1列也会有四种状态，所以第i列摆放为00的时候，可以让i+1出现00，01，10，11四种情况！后面的用下面的二维表格表示
| 00 | 01 | 10 | 11 | |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 10 | 0 | 1 | 0 | 1 |
| 11 | 1 | 0 | 0 | 0 |
由此也可得我们的转移数组g[4][4],而00，01，10，11在二进制转十进制中刚好对应0123
3.状态转移公式：f[i+1][k]+=f[i][j]*g[j][k]，首先理清这里面的i，j，k都是什么。f[i+1][k]就已经是下一个状态了，即第i列摆满，且i+1列的状态为k。而后面的f[i][j]*g[j][k],即f[i][j]想变成f[i+1][k]，就必须满足g[][]!=0才行，因为g[][]=1才表示可以转移到f[i+1][k]状态啊！
4.关于状态数组的初始化，f[1][0]=1，我们一开始放的时候其实就相当于第0列以及被铺满，且第1列一个没放；初始化为1，这个地方我是通过自己推到前几项得来的！
5.循环：首先是列数的循环，第i列的时候，我们得到的是i+1，而初始化为1，所以我们遍历为1~n；其次就是每一列可能出现的四种状态j和四种摆放方式k的循环
下面的代码里面也有解释，如果还不懂就结合代码来看或许会简单不少QWQ
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 1e7+5;
const int MOD = 1e9+7;
int n;
int g[4][4]={
{1,1,1,1},
{0,0,1,1},
{0,1,0,1},
{1,0,0,0},
};//g[当前状态][转移状态]
//转移状态：在i放满的前提下i+1的状态
int f[N][4];//状态转移数组
//f[i][j]表示前i-1已经放满，j表示第i列状态，00，01，10，11分别对应0，1，2，3
//f[i][j]的值就是到此时的个数
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
f[1][0]=1;//初始化初始状态，下一个状态是对第一列进行摆放，相当于第0列全部占满了
for(int i=1;i<=n;i++)//1~n的状态对应初始状态~最终的前一个状态
{
for(int j=0;j<4;j++)//遍历四种第i列的四种状态，即00，01，10，11
{
for(int k=0;k<4;k++)//遍历状态转移
{
f[i+1][k]=(f[i+1][k]+f[i][j]*g[j][k])%MOD;
}
}
}
cout<<f[n+1][0];//n列放满，且n+1列当前状态为00，即什么也不放
return 0;
}另外还是有些优化的
1.滚动数组优化：我写到下面的代码里面吧，这样更直观！
2.乘法相比于加减更耗时间，我们可以在进行状态转移的时候，可以先判断g[][]是否为1，详见代码吧！
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 1e7+5;
const int MOD = 1e9+7;
int n;
int g[4][4]={
{1,1,1,1},
{0,0,1,1},
{0,1,0,1},
{1,0,0,0},
};
//优化为滚动数组
//1.将初始的f[N][4]改为f[2][4]
//2.将所有的f[这个位置&1][]即可
//3，记得每一轮状态转移开始前，将下一个状态对应的数组元素初始化为0
int f[2][4];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
f[1][0]=1;
for(int i=1;i<=n;i++)
{
memset(f[i+1&1],0,sizeof f[0]);
// 将下一个状态对应的数组元素初始化为 0
// (i + 1) & 1 确定要操作的是 f[0] 还是 f[1]
// sizeof f[0] 表示要初始化的字节数
for(int j=0;j<4;j++)
{
for(int k=0;k<4;k++)
{
if(g[j][k])//判断是否为1，为1进行下面的状态转移
f[i+1&1][k]=(f[i+1&1][k]+f[i&1][j])%MOD;
}
}
}
cout<<f[n+1&1][0];
return 0;
}