摘要：
标题描述了一堵尺寸为2*n的墙，现在需要铺设2种规格的瓷砖。瓷砖规格分别为2*1和2*2。请计算摊铺方法的总数。示例输入Copy32812示例输出Copy31712731想法：这是一个递归问题，主要是查找递归规则，但我很傻！我找不到参考：https://www.jianshu.com/p/253d948b2bb3动态编程，但我的输出超出限制：https://blog.csdn.net/weixin_43207025/article/details/89602338在做递归问题时，通常的做法是先看特殊情况和终止条件，然后找到递归公式。因此，f（n-2）需要乘以2。如果更改三个瓷砖的铺设方法，显然可以从前面的递归中获得。
题目描述
有一块大小是 2 * n 的墙面，现在需要用2种规格的瓷砖铺满，瓷砖规格分别是 2 * 1 和 2 * 2，请计算一共有多少种铺设的方法。
输入
输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。
输出
输出一共有多少种铺设的方法，每组数据的输出占一行。
样例输入 Copy
3
2
8
12样例输出 Copy
3
171
2731
思路：这是一道递归题，主要要找到递归规律，但是我笨！我找不到
参考：https://www.jianshu.com/p/253d948b2bb3
动态规划法，但是我输出超限了：https://blog.csdn.net/weixin_43207025/article/details/89602338
做递归题目时，通常做法都是先看特殊情况与终止条件，再找递推公式。这道题很明显，当n=1是终止条件，n=2时候是特殊情况，原因是有两种规格的瓷砖，当n=1推到n=2时候需要考虑到有2*2规格的瓷砖，而当n>2时候，观察一下增加一列如何求得铺的地砖，我的想法是，增加一列有分两种情况，若是之前铺瓷砖的方法不变，那铺设的方法就是f(n-1)，第二种情况之前的铺瓷砖的方式进行改变，如果是改两块瓷砖的铺设方法，那么就是f(n-2)，而如果是一个2*2的墙面，你可以用两种方法，一种是横着放两块瓷砖，一种是直接放一块2*2的瓷砖，注意 这里不是三种方法，因为直接竖着放两块瓷砖的方法其实是属于第一种情况的。
因此f(n-2)是需要乘2的，若是改三块瓷砖的铺设方法，那显然可以由之前的递归所得到。
因此递归公式就是 f(n)=f(n-1)+f(n-2)*2
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
int f(int x)
{
if(x==1)
{
return 1;
}
if(x==2)
{
return 3;
}
return f(x-1)+2*f(x-2);//知道这个规律那还不简单？
}
int main()
{
int n;
cin >> n;
while(n--)
{
int m;
cin >> m;
cout << f(m) <<endl;
}
return 0;
}