1.题目描述

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

2*n 表示2行n列的矩形

2.分析，类似斐波那契数列

a.横着覆盖：当第一行的前两列被横着覆盖，第二行的前两列也只能横着覆盖，所以需要找到剩下的2 *（n-2）矩形的覆盖方法总数
b.竖着覆盖：第一列被覆盖，所以需要找到剩下的2 *（n-1）矩形的覆盖方法总数

    //1.递归
    public static int rectCover(int n) {
        if (n <= 0) return 0;
        if (n == 1 || n == 2) return n;
        return rectCover(n - 1) + rectCover(n - 2);
    }