第十三届蓝桥杯c++b组-积木画

题目描述
小明最近迷上了积木画，有这么两种类型的积木，分别为 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();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25