【剑指offer-解题系列(11)】矩形覆盖
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
分析
2*1的方格,只有1种覆盖方式
2*2的方格,有2种覆盖方式.
。。。
2*n的方格,前2*1格可以竖着放,
也在前2*2格横着放,最终a[n]=a[n-1]+a[n-2]
代码实现
int rectCover(int n) {
if(n==0)return 0;
if(n==1)return 1;
if(n==2)return 2;
return rectCover(n-1)+rectCover(n-2);
}