样例

输入样例：
3
输出样例：
5

算法1

比较“玄学”，难在初始化和状态表达。

时间复杂度$O(n)$

C++ 代码

#include<iostream>
using namespace std;
const int mod=1e9+7;
long long n,f[3];
// 前i个长的画布突出情况为0；无突出，1：有一个突出，2：有两个突出的情况
// f[i][0]=f[i-1][0]+f[i-1][2];
// f[i][1]=f[i-1][0]*2+f[i-1][1]
// f[i][2]=f[i-1][1]+f[i-1][2]+f[i-1][0]

int main()
{
     cin>>n;
    f[0]=1;f[1]=2;f[2]=2;
    for(int i=1;i<n;i++)
    {
        int a=f[0],b=f[1],c=f[2];
        f[0]=c%mod;
        f[1]+=2*a;
        f[1]%=mod;
        f[2]+=b+a;
        f[2]%=mod;
    }
    cout<<f[0];
    return 0;
}