很简单一道题, 写它是因为想水一篇博客 勾起了我的回忆
首先, 求斐波那契数列, 一定 不 要 用 递归 ! 依稀记得当年校赛, 我在第一题交了20发超时, 就是因为用了递归, 递归时大量的出入栈操作必然比循环时间来得久
这题估摸着是每个测试样例就一个数, 记忆化的优势显示不出来, 但还是要认真看题 严格要求自己
- 记忆化搜索
vector<int> dp;
int climbStairs(int n) {
if (dp.size() <= 2) {
dp.push_back(1);
dp.push_back(1);
}
if (n < dp.size())
return dp[n];
else {
for (int i = dp.size(); i <= n; ++i) {
dp.push_back(dp[i-1] + dp[i-2]);
}
}
return dp[n];
}
定义一个外部变量保存dp的值, 这样做的好处是只有当n > 目前数组的长度后才需要考虑继续添加新项
- 通项公式
交完题去看题解发现居然有这种骚操作
首先, 斐波那契数列的递推方程是差分方程 :
\[f\left( n \right) -f\left( n-1 \right) -f\left( n-2 \right) =0 \tag{1}
\]
\]
其特征方程为 :
\[\boldsymbol{x}^2-\boldsymbol{x}-1=0\tag{2}
\]
\]
解得 :
\[\boldsymbol{x}_1=\frac{1+\sqrt{5}}{2}, \boldsymbol{x}_2=\frac{1-\sqrt{5}}{2}\tag{3}
\]
\]
写出通解, 代入初值, 求得通项公式 :
\[\boldsymbol{f}\left( \boldsymbol{n} \right) =\frac{1}{\sqrt{5}}\left[ \left( \frac{1+\sqrt{5}}{2} \right) ^{\boldsymbol{n}}-\left( \frac{1-\sqrt{5}}{2} \right) ^{\boldsymbol{n}} \right]\tag{4}
\]
\]
然后直接输出就可了
int climbStairs(int n) {
return (int)((double)1/(sqrt(5)) * (pow((1 + sqrt(5))/2, n + 1) - pow((1 - sqrt(5))/2, n + 1)));
}