有一个大小是 2 x n 的网格，现在需要用2种规格的骨牌铺满骨牌规格分别是 2 x 1 和 2 x 2，请计算┅共有多少种铺设的方法

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

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

这道题我用的是DFS（这题也可找规律和DP解决）首先在一个2*n（row = 2，column = n）嘚空间中放置的方式有3种，一个种正方形放置一种是长方形正放（2 * 1），另一种是长方形侧放置（1 * n）所以，个数就是正方形放置的个數+长方形正放放置的个数+ 长方形侧放放置的个数 = 总数但是在第一次提交代码的时候TLE了。然后我们可以想，这个空间的高度（row）是2如果长方形侧放一个之后，下面如果有剩余的空间必然也是侧放一个长方形，其实就等于一个正方形。所以长方形侧放的个数 = 正方形放置的个数，所以只要将正方形的个数乘于2即可减少一层的递归即 正方形放置数 * 2+长方形放置数= 总数，以下为AC代码