一、题目描述
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案 需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
二、我的题解
func fib(n int) int {
x, y := 0, 1
if n == 0 {
return 0
} else {
for j := n; j > 0; j-- {
x, y = y, (x+y)%1000000007
}
return x
}
return 0
}
这个方法叫做 动态规划：
斐波那契数的边界条件是 F(0)=0 和 F(1)=1 。当 n>1 时，每一项的和都等于前两项的和，因此有如下递推关系：
F(n)=F(n-1)+F(n-2)
由于斐波那契数存在 递推关系，因此可以使用 动态规划 求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1) 。
根据状态转移方程和边界条件，可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n-1) 与 F(n-2) 有关，因此可以使用**「滚动数组思想」**把 空间复杂度优化成 O(1) 。
上述代码：
-
时间复杂度：O(n) 。
-
空间复杂度：O(1) 。
三、更好的题解
可以利用 矩阵乘法 将时间复杂度降低到 O(logn) ，具体请参考 LeetCode 给出的这道题的官方题解。
四、其实，刚看到这道题的时候，我的思路是“递归函数”
func fib(n int) int {
if n <= 1{
return n
}else{
return (fib(n-1)+fib(n-2))%1000000007
}
}
但是，由于这个方法太慢啦，以至于超出运行时间：
解释：
由于递归式使用了运算符，每次重复的调用都使得运算的链条不断加长，系统不得不使用栈进行数据保存和恢复。
如果每次递归都要对越来越长的链进行运算，那 速度极慢 ，并且可能栈溢出，导致程序奔溃。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/118991.html
