矩形覆盖

题目描述

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

解题思路

推导后是斐波那契数列

• f(1) = 1;
• f(2) = 2;
• f(3) = 3;
• f(4) = 5;
• ...
• f(n) = f(n-1) + f(n-2)

public class Solution {
    public int RectCover(int target) {
        if (target < 1)
            return 0;
        if (target == 1)
            return 1;
        int tmp1 = 1;
        int tmp2 = 1;
        target -= 1;
        while (target != 0) {
            int tmp = tmp1 + tmp2;
            tmp1 = tmp2;
            tmp2 = tmp;
            target--;
        }
        return tmp2;
    }
}