矩阵覆盖

题意

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

样例

对于一个 2 * 3 的矩阵，返回 3。

思路

1. 当 n 为 1 时，也就是 2 * 1 的大矩阵，只有一种方法：
   

2. 当 n 为 2 时，也就是 2 * 2 的大矩阵，有两种方法：
   
   

3. 当 n 为 3 时，也就是 2 * 3 的大矩阵，有三种方法：
   
   
   

4. 当 n 为 4 时，也就是 2 * 4 的大矩阵，应该有几种方法呢？
   4.1 根据原来 n = 3 时的内容，向右扩展一个 2 * 1 的矩阵，即：||||、=||、|=|。
   4.2 根据原来 n = 2 是的内容，向右扩展一个 = 形状的矩阵，即：==、||=。

你可以自己推导下 n = 5 时的情况，也是同样的规律。

规律为： f(n) = f(n-1) + f(n-2) (n > 3)

代码实现

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

原题地址

牛客网：矩阵覆盖