这是一个简单的动态规划题，虽然我还不知道什么是动态规划，但当我理解这个题后就是找规律，找到规律一切就出来了
【问题描述】 小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2 个单位面积）和 L 型（大小为 3 个单位面积）：
同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？ 积木可以任意旋转，且画布的方向固定。
【输入格式】 输入一个整数 N，表示画布大小。
【输出格式】 输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取 模后的值【样例输入】 3
【样例输出】 5
【样例说明】 五种情况如下图所示，颜色只是为了标识不同的积木：
【评测用例规模与约定】 对于所有测试用例，1 ≤ N ≤ 10000000.
问题分析;
先画图找规律，
当n等于0时：也就是没有积画，可以认为是一种方式
当n等于1时：有1种排列方式
当n等于2时：有2种排列方式
当n等于3时：有5种排列方式，这些比较简单，大家可以自己画图理解
当n等于4时：我们可以用一种排列规律来思考，
n等于4时的排列方式是：
在2*3的积画的基础上加一个2*1的积画
在2*2的积画的基础上加一个2*2的积画
在2*1的积画的基础上加一个2*3的积画
在2*0的积画的基础上加一个2*4的积画
由画图和分析可知：
……
2*n的积画有2种情况（找到规律了）
（前提是确保不重不漏）
例如n等于4时：
F[4]表示n等于4时有几种排列方式，
F[4]=F[3]*1+F[2]*1+F[1]*2+F[0]*2
=5*1+2*1+1*2+1*2
=11
由此可以得到规律：
F[n]=F[n-1]*1+F[n-2]*1+2*F[n-3]+2*F[n-4]+2*F[n-5]+……+2*F[0]
F[n-1]=F[n-2]*1+F[n-3]*1+2*F[n-4]+2*F[n-5]+2*F[n-6]+……+2*F[0]
两式相减得：
F[n]-F[n-1]=F[n-1]+F[n-3]
F[n]=2*F[n-2]+F[n-3]
得到公式后就好算了
我们知道初始值：
F[0]=1,F[1]=1,F[2]=2,
来看代码实现：
#include <stdio.h> #define mod 1000000007 int main(int argc, char* argv[]) { // 请在此输入您的代码 long long n = 0; long long a, b, c, d; a = 1，b = 1, c = 2; scanf("%lld", &n); for (int i = 3; i <= n; i++) { d = (c * 2 + a) % mod; a = b; b = c; c = d; } printf("%lld", d); return 0; }
注意，这里没有用数组来实现，因为数据太大，创建一个数组占用的空间太大，我用的变量代换
a相当于F[0]，b相当于F[1]，c相当于F[2],
a相当于F[n-3]，b相当于F[n-2]，c相当于F[n-1],d相当于F[n],
如果还是不理解，可以创建数组，将a,b,c,d 代换成数组去写，更容易理解
然后带入公式求解就ok了，注意题目要求，每步要取模。
我自己也是看讲解看了好多遍，动手画了好几遍，才理解这道题，所以一定要动手去写，
多做多看！
多做多看！
多做多看！
