同样，这道题本质也是 Fibonacci 数列。
假设现在有 n*2 个小矩形组成的大矩形，可以有 f(n)种填充方法。如果用 2*1 的小矩形摆在最开始，那么就有两种方案，一种是一块占据 1*2 一列，另一种是两块占据 2*2 两行，这样，剩下的就是 f(n-1)和 f(n-2) 两种了。
实现代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int rectCover(int number) {
if(number<=0) return 0;
if(number==1) return 1;
if(number==2) return 2;
int first=1;
int second=2;
for(int i=3;i<=number;i++){
int third=first+second;
first=second;
second=third;
}
return second;
}
};
|