矩形覆盖
一、问题描述
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
二、算法思想
这题是通过递归的问题，类似于斐波那契数列问题，找到数列递推关系，加上初始值，可以用递归解决。当然也可以通过关系式推导出通项，利用迭代解决。
我们的目标是将用2x1的小矩形将其覆盖，小矩形覆盖的方式无非就两种，横着和立着。
n=0 F(0)=0
n=1 F(1)=1，只有一种安放方式。
n=2 F(2)=2，横着和竖着两种。
n>=3 F(n)=F(n-1)+F(n-2)，（1）当第一块选择竖着放，那么接下来的2x(n-1)的矩形仍然需要用2x1的矩形来覆盖，那么就是F(n-1)；（2）当第一块选择横着放，那么第二块也必须横着放才能填满下面的空缺。接下来的2x(n-2)的矩形面临同样的问题。
三、算法实现
3.1、C++递归实现
class Solution {
public:
int rectCover(int number) {
if(number<=0)return 0;
if(number==1)return 1;
if(number==2)return 2;
return rectCover(number-1)+rectCover(number-2);
}
};3.2、C++迭代实现
class Solution {
public:
int rectCover(int number) {
if(number<=0)return 0;
if(number==1)return 1;
if(number==2)return 2;
int pp=1;
int p=2;
int result=0;
for(int i=3;i<=number;i++){
result=pp+p;
pp=p;
p=result;
}
return result;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
