矩形覆盖

题目描述

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

题解

分析：

如果在左上角先竖着放1个，那么剩下的覆盖的方法 F(N) = F(N-1)

如果在左上角先横着放1个，那么左下角必须也横着放一个，那么剩下的覆盖的方法 F(N) = F(N-2)

所以，F(N) = F(N-1) + F(N-2)

斐波那契数列...

public int RectCover(int target) {
    if (target == 0 || target == 1 || target == 2)
        return target;

    int pre1 = 1;
    int pre2 = 2;

    int res = 0;
    for (int i = 3; i <= target; i++) {
        res = pre1 + pre2;
        pre1 = pre2;
        pre2 = res;
    }
    return res;
}