题目描述
小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2 个单位面积）和 L 型（大小为 3 个单位面积）：

同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？ 积木可以任意旋转，且画布的方向固定。

输入格式
输入一个整数 N，表示画布大小。
输出格式
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入
3
样例输出
5
提示
五种情况如下图所示，颜色只是为了标识不同的积木：

思路：dp(直觉），然后我想着行都是两行，那我设置dp[i]表示前i列得到的最多方案数。在我找该状态与前面状态的关系中，那个提示给了我很多启发。
然后
假设前i-1列排满后排满i列有几种情况
假设前i-2列排满后排满i列有几种情况
假设前i-3列排满后排满i列有几种情况
不过我写了许多递推公式，就是不对。后来看到了一个贼nb的图解。（数学功底有待提高，我都是靠脑子推，这大佬用公式推）。
dp[i] = dp[i-1]*2+dp[i-3]
图解-积木画

AC代码：

import java.util.Scanner;
public class Main {static int N = 200005;static int[]a = new int[N];static int[]b = new int[N];public static void main(String[] args) {new Main().solve();}void solve() {int mod = 1000000007;Scanner sc = new Scanner(System.in);int n = sc.nextInt();int dp[] = new int [n+5];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;}System.out.print(dp[n]);sc.close();}
}