剑指offer

Problem

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

Solution

2*1的矩形只有1种方法

2*2的矩形有2种方法

一个2*n的矩形可以有两种拆分

  • 2*1 + 2*(n-1)
  • 2*2 + 2*(n-2)

所以这又是一个斐波那契问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class  {
public:
int rectCover(int number)
{
if(number <=2)
{
return number;
}

int prev1, prev2, sum;
prev1 = 1;
prev2 = 2;

for(int i = 3; i <= number; ++i)
{
sum = prev1 + prev2;
prev1 = prev2;
prev2 = sum;
}
return sum;
}
};