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