题目链接:https://www.lanqiao.cn/problems/2110/learning/

动态规划一直是我的弱项,这个题其实是一个很简单的动态规划的题非板子题。

这个题的精髓在于递推上面。

下面来仔细分析一下。

首先  当n =1,2,3 时  s = 1,2,5  这是可以得到的。
当每次增加一列时,我们总能得到两倍的  ai-1 这是易知的。  那么问题就在于什么时候去得到更多的L型组合呢
首先L型组合是在某一  组合下  每次增加三列可以得到。  因为L型的组合不能单独出现。而是成双出现。

这样  在确定前三项之后, 我们总能通过 a[i] = a[i-1]*2 + a[i-3] 来得到。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 1e7+10;
const int mod = 1000000007;
int a[nn];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin>>n;
	a[1]=1,a[2]=2,a[3]=5;
	for(int i=4;i<=n;i++)
	{
		a[i] = a[i-1]*2%mod+a[i-3]%mod,a[i]%=mod;
	}
	cout<<a[n]<<endl;
}