剑指Offer:矩形覆盖

题目

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

分析

就以上图为例,当我们用2*1的小矩形去覆盖大矩形的最左边时有两种选择:横着放或者竖着放。
如果竖着放在,右边还剩下一个长为7的矩形
矩形覆盖1.jpg
如果横着放在,右边还剩下一个长为6的矩形
矩形覆盖2.jpg
如果我们规定原来长度为8的矩形为f(8),同理长度为7的矩形为f(7),长度为6的矩形为f(6),所以在这种情况下f(8)=f(7)+f(6);
So,这也是一道斐波那契数列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int RectCover(int target) {
if(target <= 1)
return target;
int a = 1;
int b = 2;
int c = b;
for(int i = 0;i < target-2;i++){
c = a + b;
a = b;
b = c;
}
return c;
}
}