首先介绍斐波那契的递推式
$$
F(i)=\begin{cases}
0,i=0\\\
1,i=1\\\
F(i-1)+F(i-2),i>1
\end{cases}
$$
利用这个式子,我们可以简洁地写出代码,但我们追求更短,就有一个问题:
- 我们已知 $0$ 和 $1$ 时的值,所以我们循环次数是 $(n-1)$ 次;
- $0$ 和 $1$ 时要写特判
这两点严重影响我们的代码长度,所以我们要使用一些歪门邪道来使我们的代码更短,解决循环次数和特判的问题,最终我决定——倒推一位斐波那契数
将递推式反过来得到 $F(i)=F(i+2)-F(i+1)$ ,这样我们就可以强行得到 $F(-1)=1$ ,然后就完美解决了问题,得到了非常短的代码:
python代码
class Solution(object):
def Fibonacci(self, n):
res, prv = 0, 1
for i in range(n):
res, prv = res + prv, res
return res
题解中的顺序搞反了吧
class Solution(object):
def Fibonacci(self, n):
res, prv = 1, 1
for i in range(n-1):
res, prv = prv, res+prv
return res
WOC+NB