题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：
可以从第n-1到一步到n，这样的话有多少种方案覆盖到n-1就有多少种方案覆盖到n，另外我们也可以从n-2覆盖到n，有多少种方案覆盖到n-2就有多少种方案覆盖到n.？可以这样认为2*1的矩形有两种可能;1)竖着2*1 2）横着 此时必须是两块2*1的矩形拼成2*2 此时就好理解了
也可以也可以举例子归纳：
分别为当n=1时 1种
n=2时 2种方式
n=3时 3种方式
n=4 时 5种方式
f(n) = f(n-1) + f(n - 2)， (n > 2)
推广：
相应的结论应该是：
（1）1 * 3方块 覆 盖3*n区域：f(n) = f(n-1) + f(n - 3)， (n > 3)
（2） 1 *4 方块 覆 盖4*n区域：f(n) = f(n-1) + f(n - 4)，(n > 4)
更一般的结论，如果用1*m的方块覆盖m*n区域，递推关系式为f(n) = f(n-1) + f(n-m)，(n > m)。
参考;https://www.nowcoder.com/profile/2951934/codeBookDetail?submissionId=16796833
类似之前的文章：
30.斐波那契数列https://blog.csdn.net/heda3/article/details/86773270
31.跳台阶https://blog.csdn.net/heda3/article/details/86773998
递归解法：
class Solution {
public:
int rectCover(int number) {
if (number < 1)
{
return 0;
}
else if (number == 1 || number == 2)
{
return number;
}
else
{
return rectCover(number-1) + rectCover(number-2);
}
}
};
迭代解法：
1需要辅助数组
class Solution {
public:
int rectCover(int number) {
int rC[number+1];
rC[1]=1;
rC[2]=2;
if (number <= 1)
{
return number;
}
for(int i=3;i<=number;i++)
{
rC[i]= rC[i-1]+ rC[i-2];
}
return rC[number];
}
};
迭代：递推解法1
2不需要辅助数组，需要3个变量
class Solution {
public:
int rectCover(int number) {
int rC1=1,rC2=1,rC3=1;
if(number <= 1)
{
return number;
}
for(int i=2;i<=number;i++)
{
rC3=rC1+rC2;
rC1=rC2;
rC2=rC3;
}
return rC3;
}
};
注意：如果n=0那么返回是0
错误代码
class Solution {
public:
int rectCover(int number) {
if(number<=0)
return 1;//像这样是错的
int temp1=1,temp2=1,temp3=1;
while(--number){
temp3=temp1+temp2;
temp1=temp2;
temp2=temp3;
}
return temp3;
}
};
递推2
需要两个变量
class Solution {
public:
int rectCover(int number) {
if ( number < 1 )
return 0;
int g = 1, f = 2;
while ( --number )
{
//只需要两个变量
f = f + g;
g = f - g;
}
return g;
}
};
