1.问题

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

2.思路

当target = n

上图中，如果填充第一个2n（绿色）的如图所示，那么就变成了RectCover(n-1)问题
下图中，如果填充第一个2n（绿色）的如图所示，那么第二块砖必定是蓝色的砖块，问题变成了RectCover(n-2)问题.

3.代码

package test1_10;
/* * @author qianliu on 2019/4/21 14:45 * @Discription: * 1.问题：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ */
public class Test10 {
    /* * 1.RectCover(1)=1 * 2.RectCover(2)=2,一种是横着放两块木头，一种是竖着放两根木头 * 3.RectCover(n)需要考虑: * 横着放第一块木头，那么就变成了第2块木头必须横放，后面就是RectCover(n-2) * 竖着放第一块木头，那么牛变成了RectCover(n-1) * */
    public static int RectCover(int target) {
        if(target <= 2) return target;

        return RectCover(target-1) + RectCover(target-2);
    }

    public static void main(String[] args) {
        System.out.println(RectCover(7));
    }
}