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];
    }
};