Question

C++编程题：帮我理解一下这个代码

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

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

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

Sample Input
3
2
8
12

Sample Output
3
171
2731
代码：
#include <iostream>

using namespacestd;
intdig[40];
int main()
{
dig[1]=1;
dig[2]=3;
for(inti=3;i<=30;i++)------------》特别这里
dig[i]=dig[i-1]+2*dig[i-2];-------------》
intn;
while(cin>>n)
{
while(n--)
{
intm;
cin>>m;
cout<<dig[m]<<endl;
}
}
return0;
}

Answer 1

首先分析一下这个题目，题目分析清楚了，代码也就清楚了。

我们假设摆2*N块砖有dig[n]中方法，根据下面的分析，我们可以dig[n]递归到dig[n-1]和dig[n-2]上，dig[n]可以分解为上图的三种摆法：

1. 最后选一块2*1的砖，竖着放：  前面2*(N-1)块砖,一共有dig[n-1]种摆法

2. 最后选一个2*2的砖，（横竖放都一样）：前面有2*(N-2)块砖，一共有dig[n-2]种摆法

3. 最后选一块2*1的砖，横着放（横着放的2*1的砖必然是成对出现的）：前面有2*(N-2)块砖，一共有dig[n-2]种摆法

所有，2*N的总摆法数，就是一个递归计算的过程,

dig[n]=dig[n-1]+dig[n-2]+dig[n-2] = dig[n-1]+2*dig[n-2];

Answer 2

问题虽然简单，但是蕴含了动态规划的思想。

比如 假如长度是N ，那么可以将问题缩小成 1 ： N-1长度 加一块 竖着的 2乘1 ；
2： N-2长度 加一块 2乘2
3：N-2长度 加两块横着的1乘2

通过上面三种情况，可以从低维度（N等1或2） 依次推出其他的维度情况。

Answer 3

for(inti=3;i<=30;i++) 从i=3 开始 一直执行到29 到 i=30 跳出循环

dig[i]=dig[i-1]+2*dig[i-2] 从=3开始 把d[i]的前一项加上d[i]的第前二项的2位赋给d[i]，举列：i=3

d[3]=d[2]+2*d[1]=5 一直执行到29 到 i=30 跳出循环