D - Tiling_easy version

HDU - 2501

有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设的方法。
Input
输入的第一行包含一个正整数T（T<=20），表示一共有 T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示网格的大小是2行N列。
Output
输出一共有多少种铺设的方法，每组数据的输出占一行。
Sample Input
3
2
8
12
Sample Output
3
171
2731

解法：瓷砖问题，基础情况有三种，竖放一个2x1、横放两个2x1、放一个2x2，开始用递归，时间暴了，然后正着算，对于第n个单位可以看成第n-1个单位加一个2x1，或者第n-2个单位放一个2x2或两个2x1，所以a[n] = a[n-1] + a[n-2]*2。

代码：

#include<iostream>
using namespace std;
int a[35];
int main()
{
    int num;
    cin>>num;
    a[1]=1,a[2]=3;
    for(int i=3;i<=30;i++)
        a[i]=a[i-2]*2+a[i-1];
    for(int i=0;i<num;i++){
        int n;
        cin>>n;
        cout<<a[n]<<endl;
    }
}