解题思路:

首先这个题肯定是用动态规划来做的,正好它也符合动态规划做题的思想,无后效性也满足所以我们用动态规划做会好做一点.

那怎么想这个题呢,首先它是二维的一个矩阵模式,并且有摆放还是有顺序的,所以我们如果要用二维dp来做还确实不好做,拿我们所幸直接用一维来简化拼积木的过程,但是怎么简化呢.

我们先来看下题目给的案例:

首先我们直接来看三阶的,第一个和第二个我们可以发现I型积木拼放的方式是有2种的,或者看一和四都行,然后L型积木的拼接方式是1种看三和五(你把他们两个反转过来就是一种),那我们不妨想的简单一点所以递推公式就是:dp[i]=dp[i-1]*2+dp[i-3];

证明的方法就是我们刚才的思想过程,我们讲二维的矩阵看成了一维的,所以I型积木就是等于1个方格,所以我们记为i-1,L型积木就是等于1.5个方格,但是L型积木不能单独出现,必须成双的出现,所以我们记为i-3,又由于I型积木出现在一个位置有两种方式,所以我们乘以二,L型积木出现只有一直方式我们乘以1,就结束了。

但是我们还要进行初始化前三个:

当i等于1的时候dp就是1,这个没啥说的,只能放一种I型不管咋放都一样.

当i等于2的时候dp是2,因为可以放两个I型,可以水平放可以竖直放2种.

当i等于3的时候就是题目当中的情况dp等于5,

参考代码:

#include<stdio.h>
#include<string.h>
#define mod 1000000007
int dp[10000005];
int main()
{
	int n;
	scanf("%d",&n);
	memset(dp,0,sizeof(dp));
	dp[1]=1,dp[2]=2,dp[3]=5;
	for(int i=4;i<=n;i++)
	{
		dp[i]=(dp[i-1]*2%mod+dp[i-3]%mod)%mod;
	}
	printf("%d\n",dp[n]);
	return 0;
}