一、题目描述

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

二、算法分析

如果是1x2的，只有一种覆盖方法，如果是2x2的，则有两种，2xn的矩形由前两种组合而成

定义f(n)表示2xn的矩阵的覆盖法，那么如同前面的跳台阶一样，只有两种可能，最后剩下的是1x2的矩形或则是2*2的矩形，所以f(n)=f(n-1)+f(n-2)

此处还是采用记事本法，记录每一种的覆盖数数，避免重复计算，

三、算法实现

public class Solution {
    int[] log = new int[1000];
    public int RectCover(int target) {
        int n = target;
        if(n==0|n==1||n==2)
            return n;
        if(log[n]==0)
            log[n]=RectCover(n-1)+RectCover(n-2);
        return log[n];
    }
}

文章为个人编辑，如有错误，欢迎指正！