题目链接地址： ?pid=1390
题目1390：矩形覆盖
时间限制：1 秒内存限制：32 兆特殊判题：否提交：1657解决：1057 题目描述： 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ 输入： 输入可能包含多个测试样例，对于每个测试案例， 输入包括一个整数n(1<=n<=70)，其中n为偶数。 输出： 对应每个测试案例， 输出用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，，总共有的方法数。 样例输入： 4 样例输出： 5
思路分析： 重在分析，举例思考 2*n的覆盖方法情况（f(n)），第一个2*1小矩形覆盖最左边的时候： （1） 第一个2*1小矩形选择竖着放，那么还剩下2*n-1的区域，而2*n-1区域的覆盖数目是f(n – 1)； （2）第一个2*1小矩形选择横着放，则下面必须再放一个2*1小矩形，同时还剩下2*n – 2区域，而2*n-2区域的覆盖数目是f(n – 2)；
所以总数为f(n) = f(n-1) + f(n-2) . f(1)=1 对于f(0).通过f(2)=f(1)+f(0)=2知道 f(0)=1. 参考前一篇博文。
代码：
/【剑指Offer面试题】 九度OJ1390：矩形覆盖———————————– Author:牧之丶 Date：2015年Email:bzhou84@163.com */ using namespace std;#define N 75long long rectangleNum[N];long long RectangleNum(int n){}int main(){}/***/
并且为之实践了关怀和付出的善举。对于我性情中的易感和怨薄，
