牛客JZ10 矩阵覆盖

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

比如n=3时，2 * 3的矩形块有3种覆盖方法：

思路：这种题目先找个规律，再判断怎么写吧。

n = 2：有2种，横2、竖2

n = 3：3种，如题

n = 4：5种，如下（1代表竖着的，=代表两个横着的）

? 1111 11= =11 1=1 ==

n = 5：8种，如下

? 11111 111= =111 1=11 11=1 =1= ==1
1==

n = 6：共13种，如下

? 111111 1111= =1111 1=111 11=11 111=1 ==11

? 1==1 11== =11= =1=1 1=1= ===

这样好像就能发现一点儿规律了，8 = 5 + 3， 13 = 8 + 5，即f(n) = f(n - 1) + f(n - 2)，熟悉的斐波那契数列。这样就很简单了。

public class Solution {
    public int rectCover(int target) {
        if (target == 1 || target == 2 || target == 0)
            return target;
        
		int a = 1, b = 2;
        int c = 3;
        for (int i = 4; i <= target; i++) {
            a = b;
            b = c;
            c = a + b;
        }
        
        return c;
    }
}