第十题：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：每个2*1的小矩形可以横着放，也可以竖着放，如图所示：
竖着放
横着放
当第一个小矩形是竖着放时，大矩形的长和这个小矩形的长度之差为n-1，即剩下的大矩形由n-1个竖放小矩形组成，剩下的矩形放法有f(n-1)种。
当第一个小矩形是横着放时，大矩形的长和这个小矩形的长度之差为n-2，即剩下的大矩形由n-2个竖放小矩形组成，剩下的矩形放法有f(n-2)种。
即f(n)=f(n-1)+f(n-2)，同理f(n-1)=f(n-2)+f(n-3)....f(3)=f(2)+f(1)，f(2)=2，f(1)=1，f(0)=0。由此可见，此题也是斐波拉契数列求值问题，与之前的斐波拉契数列问题一样，由于存在栈溢出现象，不能直接使用递归，而是使用循环的方式实现。
Python：
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
elif number == 1:
return 1
elif number == 2:
return 2
else:
f1 = 1
f2 = 2
while number > 2:
number -= 1
sum = f1 + f2
f1 = f2
f2 = sum
return sum
Java:
public class Solution {
public int RectCover(int target) {
if(target == 0)
return 0;
else if(target == 1)
return 1;
else if(target == 2)
return 2;
else{
int f1 = 1;
int f2 = 2;
int sum = 0;
while(target > 2){
target -= 1;
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}
}
}
