剑指 offer 笔记 10 | 矩阵覆盖

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

思路分析
1）先考虑特殊情况，当 n < 1时，显然是不能满足，那么只能返回 0 ；
2）当 n = 1 时，只能有一种情况；

image.png

3）当 n = 2 时，有两种情况；

1 2

4）当 n = 3 时，如下；

3

5）继续归纳，当 n = 4，也就是在 4）步骤的基础上，多加两种情况。

5

归纳总结规律，f(1) = 1; f(2) = 2; f(3) = f(1) + f(2) = 3;
f(4) = f(3) + f(2) = 5;....f(n) = f(n-1) +f(n-2) (n>2)。

代码如下：

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

参考文献：https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6