矩形覆盖

题目描述

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

思路解析

  • 先把2*8的覆盖方法记为f(8)
  • 竖着放还有f(7)
  • 横着放f(6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class {
public int RectCover(int target) {
if(target == 1)
return 1;
if(target == 2)
return 2;
int firstCover = 1;
int secondCover = 2;
int result = 0;
for(int i = 3; i <= target; i++){
result = firstCover + secondCover;
firstCover = secondCover;
secondCover = result;
}
return result;
}
}