剑指offer----矩形覆盖
程序员文章站
2022-04-03 16:53:53
...
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
//如上图所示,n大于3时,有两种可能,红色部分为已经使用小矩形覆盖的部分,
//蓝色部分为未使用小矩形覆盖的部分,两部分叠加即可
int rectCover(int number) {
if(number==1)return 1;
else if(number==2)return 2;
else if(number==0)return 0;
return rectCover(number-1)+rectCover(number-2);
}
//非递归法,和跳台阶差不多,有两种可能,当n>3时,相加两种可能即可,
//和上面递归方法的图一样,只有那两种可能性。
int rectCover(int number) {
if(number==1)return 1;
else if(number==2)return 2;
else if(number==0)return 0;
vector<int> vec(number,0);
vec[0]=1;
vec[1]=2;
for(int i=2;i<number;++i)
{
vec[i]=vec[i-2]+vec[i-1];
}
return vec[number-1];
}
上一篇: 矩形覆盖
下一篇: hihoCoder1040:矩形判断