矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？。
n<=39（点我直接练习）
分析
本题是剑指offer中的最后一道以循环和递归来解决的问题，其实做了这几道题，他们的共同点并不是使用何种数据结构，而是找规律。此题的规律看起来是需要一点平面的组合技巧，实际上，对于规律来说，递推出前面几项，就可以基本上得到大致的规律。输入为1，就1中；输入为2，那么就是一个田字形，我们可以有两种填法；输入为3，则代表又加入一列，经过枚举，发现是3种，此时猜测规律可能是前两项之和为本题的规律。再尝试输入为4时，枚举的结果是5，正是2+3。故确定规律，盘它！
使用到的知识点
C++
循环
Python
同上
题解
C++(Clang++ 3.9) : 运行时间：4ms 占用内存：620k
class Solution {
public:
int rectCover(int number) {
if(number == 1)
return 1;
if(number == 2)
return 2;
else{
int n1 = 1, n2 = 2;
int anwser = 0;
while((number-2)>0){
anwser = n1+n2;
n1 = n2;
n2 = anwser;
number--;
}
return anwser;
}
}
};
Python 2.7-运行时间：34ms ,占用内存：5732k
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
if number == 1:
return 1
if number == 2:
return 2
else:
n1 = 1
n2 = 2
anwser = 0
number = number-2
while(number>0):
anwser = n1+n2
n1 = n2
n2 = anwser
number = number-1
return anwser
偷了个懒，直接把C++的写成python风格，几乎相同的代码下，依然差了这么多的性能，不禁引发了我的思考，究竟差在哪里呢？
