1065: 小明的烦恼
2019-04-26 本文已影响0人
茶酒qqq
题目描述
小明最近新买了一个房间，为了给它做装修，想要给它铺上地砖。然而现有的地砖只有两种规格分别为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
