剑指offer-JZ10

C++
依然考察变种的斐波那契数列。
针对 的矩阵，有两种添加方法：
1-在 的所有矩阵很难后面后面，竖着添加一个，那么有 种
2-在 的矩阵后面横着添加2个，那么有 种
其中

没有可以计算得到的规律，GG。

方法一：递归

class Solution {
public:
    int rectCover(int number) {
        if(number == 1  || number == 2) return number;
        return rectCover(number-1)+rectCover(number-2);
    }
};

然而 内存超出， 可能是number 太大了， 尝试增加记忆，

class Solution {
public:
    int Fib(int n, vector<int> &dp){
        if(n==0 || n==1 ||n==2) return n;
        if(dp[n] != -1) return dp[n];
        return dp[n]=Fib(n-1, dp)+ Fib(n-2, dp);
    }
    int rectCover(int number) {
        vector<int> dp(number+1, -1);
        return Fib(number, dp);
    }
};

方法二，动态规划

class Solution {
public:
    int rectCover(int number) {
        if(number==0 || number==1 || number==2) return number;
        int tmp1=2, tmp2=1, ans;
        for(int i=3;i<=number; i++){
            ans = tmp1 + tmp2;
            tmp2 = tmp1;
            tmp1 = ans;
        }
        return ans;
    }
};

方法三，直接计算，暴力法，
时间复杂度
空间复杂度

class Solution {
public:
    int rectCover(int number) {
        vector<int> f(number+1, 0);
        f[1]=1;
        f[2]=2;
        for(int i=3;i<=number; i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[number];
    }
};