矩形覆盖

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

public class Solution {
    public int RectCover(int target) {
        // (竖) 横+竖 无重叠
        //1 : 1 + 0 =1
        //2 : 1 + 1 = 2
        //3 : 1 + 2 = 3
        //4 : 1 + 4 = 5
        //5 : 1 + 7 = 8 
        // f(0)=0;f(1)=1.f(n)=f(n-1)+f(n-2)
        if(target<0){
            return 0;
        }else if(target==1 || target==2){
            return target;
        }else return RectCover(target-1)+RectCover(target-2);
    }
}

class Solution:
    def rectCover(self, number):
        # write code here
        if number <=0:
            return 0
        elif number <=2:
            return number
        else: f0,f1=1,2
        for i in range(2,number):
            f = f0 + f1
            f0 = f1
            f1 = f 
        return f