矩形的覆盖

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

算法解析
这道题可以用斐波纳数列发现规律
n = 1, f(1) = 1
n = 2,f(2) = 2
n = 3,f(3) = 3
f(n) = f(n-1) + f(n-2);
在最后一格2*1矩形里只有两种摆法，一种是竖着放，与之相应的竖着放结束的摆法有f（n-1）种，一种是横着放，则与之相应的横着放结束的摆法有f(n-2)种，二者不会重复
语言java

递归算法

public int Rectcover(int target)
{
         if(target == 0)
               return 0;
        if(target == 1)
               return 1;
        if(target == 2)
               return 2;
        return Rectcover(target-1) + Rectcover(target -2)
}

运行效率
运行时间：622ms
占用内存：15344k

非递归算法

 public int RectCover(int target) {
        if(target == 0)
            return 0;
        if(target == 1)
            return 1;
        if(target == 2)
            return 2;
        int result1 = 1;
        int result2 = 2;
        int result = 0;
        for(int i = 3;i<=target;i++){
            result = result1+result2;
            result1 = result2;
            result2 = result;
        }
        return result;
  }

运行时间：18ms
占用内存：15332k