题解 | #矩形覆盖#

class Solution {
public:
    int rectCover(int number) {
        if(number < 1 ) return 0;
        if(number == 1) return 1;
        if(number == 2) return 2;
        return countCore(number, 1, 2);
    }

    int countCore(int n, int n1, int n2){
        if(n == 2) return n2;
        return countCore(n-1, n2, n2+n1);
    }
};

从number0开始分析：

实际上，3种以后可以考虑左边数第一个是横着放还是竖着放：
横着放，右边剩下的就是3-2 = 1个宽度；
竖着放，右边剩下的就是3-1 = 2个宽度。
即：
f(n) = f(n-1) + f(n-2)
本质是一个斐波那契数。使用tail recursion实现。递归的第一个参数为递归层深，最后一个参数传入累计结果，达到层深后返回累计结果即可。