1065: 小明的烦恼

题目描述

小明最近新买了一个房间，为了给它做装修，想要给它铺上地砖。然而现有的地砖只有两种规格分别为1米1米、2米2米，由于小明买的房间有点小，宽度只有3米，长度为N米。当然这样一个房间也足够他自己一个人住了。那么如果要给这个房间铺设地砖，且只用以上这两种规格的地砖，请问有几种铺设方案。

输入

输入的第一行是一个正整数C，表示有C组测试数据。接下来C行，每行输入一个正整数n（1<=n<=30），表示房间的长度。

输出

对于每组输入，请输出铺设地砖的方案数目。

样例输入

2
2
3

样例输出

3
5

思路

此题和1059差不多。
令f(N)为N列时不同的铺设方法

• 当N=1时，只有一种铺设方法,三个小的竖着贴，即f(1)=1;
• 当N=2时,f(2)=3; 因为上面一个大的，下面两个小的是一种，反过来是一种，全用小的拼是一种
• 当N=3时，可以分解为两个问题，先拼一列还是两列（因为拼两列可以用2 * 2的瓷砖，所以分类 ）：
  （1）拼1列时，就一种方法，拼了后剩下列数为N-1，所以f(3)=1*f(3-1)+(另一种拼的方法的数量);
  （2）拼2列时, 有两种方法，上面大下面两块小或者上面两块小下面一块大，另一种全用小的在只拼一列的情况时遇到了，就不能再重复计算了，所以乘上2。拼了后剩下列数为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一样