剑指Offer第10题：矩形覆盖

发表于 更新于 分类于

题目：我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？

解题思路：覆盖一个大小为2xn的矩形，第一步若选择横放，那么下面的也只能横放；问题退化成f(n-2)；若选择竖放，则问题退化为f(n-1) 。从而可以得到递推公式：f(n)=f(n-1)+f(n-2)

代码：

1
2
3
4
5
6
7
8
9
10
int rectCover(int number) {
    if (number < 1) return 0;
    int a=1;
    int b=0;
    while (number-->0) {
        a += b;
        b = a - b;
    }
    return a;
}