矩形覆盖

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

首先来理解一下题意，比如 n = 3 时，2*3 的矩形块有三种覆盖方法：

这道题目依旧是斐波那契数列，2*n 的大矩形，和 n 个 2*1 的小矩形，其中 target*2 为大矩阵的大小，有以下几种情形：

• target <= 0

  大矩形为 <= 2*0，直接 return 1

• target = 1

  大矩形为 2*1，只有一种摆放方法，return 1

• target = 2

  大矩形为 2*2，有两种摆放方法，return 2

• target = n

  分为两步考虑：

  • 第一次摆放一块 2*1 的小矩阵，则摆放方法总共 f(target - 1)

    

  • 第一次摆放一块 1*2 的小矩阵，则摆放方法总共为 f(target - 2)，因为摆放了一块 1*2 的小矩阵，对应下方的 1*2 摆放方法就确定了，所以为 f(target - 2)

    

代码如下

public class Solution {
    public int RectCover(int target) {
        if(target <= 0) {
            return 0;
        } else if(target == 1) {
            return 1;
        } else if(target == 2) {
            return 2;
        } else {
            return RectCover(target - 1) + RectCover(target - 2);
        }
    }
}