题目描述

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

比如n=3时，2*3的矩形块有3种覆盖方法：

思路

这题是《剑指Offer（七）：斐波拉契数列》的变种，做法和其一样，不在这里描述，详情见

class Solution {
public:
    int rectCover(int number) {
        int *dp=new int[number+2];
        dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=3;
        for(int i=4;i<=number;++i){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[number];
    }
};