剑指Offer——（10）矩形覆盖

题目描述：

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

实现如下：

//有两种放置方法 //1.左边竖着放一个，则还剩下2*(n-1) //2.左上角横着放一个，相应左下角也横着放一个，则还剩下2*(n-2) //f(n) = f(n-1) + f(n-2) //特殊情况：不存在时返回0；2*1时只有竖着放一种情况；2*2时两种情况 class Solution { public: int rectCover(int number) { if (number < 1) return 0;//特殊情况 else if(number == 1) return 1; else if (number == 2) return 2; else { int a = 1, b = 2, tmp = 0; for (int i = 3; i <= number; ++i) { tmp = a + b; a = b; b = tmp; } return tmp; } } };