1059: 贴瓷砖

题目描述

有一块大小是 2 * n 的墙面，现在需要用2种规格的瓷砖铺满，瓷砖规格分别是 2 * 1 和 2 * 2，请计算一共有多少种铺设的方法。

输入

输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。

输出

输出一共有多少种铺设的方法，每组数据的输出占一行。

样例输入

3
2
8
12

样例输出

3
171
2731

思路：

将墙面看作长为N列，宽为2的矩形，令f(N)为N列时不同的铺设方法，易知f(N-1)为N-1列时的不同铺设方法。
当N=1时，只有一种铺设方法，即f(1)=1;
当N=2时,f(2)=3; 因为两个个2 * 1的拼有两种方法，再加上一个2 * 2的，共三种
当N=3时，可以分解为两个问题，先拼一列还是两列（因为拼两列可以用2 * 2的瓷砖，所以分类 ）：

• 拼1列时，就一种方法，拼了后剩下列数为N-1，所以f(3)=1*f(3-1)+(另一种拼的方法的数量);
• 拼2列时, 有两种方法，一块2*2或者两块横着的2 * 1，拼了后剩下列数为N-2，所以f(3)=1 * f(3-1)+2 * (3-2)
  所以递推公式为 f(N)=f(N-1)+2 * f(N-2)
  终止条件是f(1)=1，f(2)=3

代码（AC）

1059: 贴瓷砖