动态规划、递归-矩形覆盖

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

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

解题思路很简单：适用于动态规划和递归
n=1时，结果为1
n=2时，结果为2
后续我们考虑n时，如果最后一格单独为竖的，就和n-1的情况一样
或者最后一格和前一格一起，搞成两个横的，那么就和n-2的情况一样
所以递归表达式就是ans[n]=ans[n-1]+ans[n-2]

递归和动态规划都可以
经测试，内存消耗二者差不多，时间上动态规划快的多

代码如下：

public class Solution {
    //动态规划
    public int RectCover(int target) {
        int[] ans=new int[target];
        if(target==0) return 0;
        if(target==1) return 1;
        if(target==2) return 2;
        ans[0]=1;
        ans[1]=2;
        for(int i=2;i<target;i++){
            ans[i]=ans[i-1]+ans[i-2];
        }
        return ans[target-1];
    }
    //递归
    public int RectCover1(int target) {
        if(target==0) return 0;
        if(target==1) return 1;
        if(target==2) return 2;
        return RectCover(target-1)+RectCover(target-2);
    }
}