剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 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
编码模板
func fib(n int) int {
}
我的解答
func fib(n int) int {
if n == 1 || n == 2 {
return 1
}
result := 0
a := 1
b := 1
for i := 2; i < n; i++ {
result = (a + b) % 1000000007
b = a
a = result
}
return result
}
优质解答
这一题求斐波那契数列的第n项，很经典的动态规划题。千万不能用递归做，不然复杂度直接爆炸。
直接利用斐波那契数列的规律来做，即F(N) = F(N - 1) + F(N - 2)，建立三个变量a,b,c分别保存F(N - 2)，F(N - 1)，F(N)，每次循环时让a=b，b=c，c=a+b（注意取模）即可。 对于n为0和1的情况单独讨论即可
func fib(n int) int {
if n==0{ //0单独讨论
return 0
}
a,b,c:=0,0,1
for n>1{ //这里写n>1，其实就是把n=1单独讨论了，n=1时直接返回c也就是1
a=b
b=c
c=(a+b)%1000000007 //取模
n--
}
return c
}
func fib(n int) int {
if n <2 {
return n
}
const mod int = 1e9 + 7
n1,n2 :=0,1
for i:=2;i<=n;i++{
n2,n1 = (n1+n2)%mod,n2
}
return n2
}
func fib(N int) int {
f0, f1 := 0, 1
for i := 0; i < N; i++ {
f0,f1 = f1,(f0 + f1) % 1000000007;
}
return f0
}
「真诚赞赏，手留余香」
kzdgt Blog
真诚赞赏，手留余香
使用微信扫描二维码完成支付
