# 题目链接
# 题目描述
求斐波那契数列的第 n 项,n <= 39。

# 解题思路
刚开始准备直接递归,发现怎么都会超出编译时间,果然递归很费时。 然后参考了题解,使用动态规划,相当于把斐波那契数变成了一个用来累加数的for循环,一直循环到n,然后返回的res值就是斐波那契数得出的最终值。
func fib(n int) int {
if n == 0 ||n == 1 {
return n
}
res := make([]int, n + 1)
res[0] = 0
res[1] = 1
for i := 2 ; i <= n ; i++ {
res[i] = (res[i-1] + res[i-2])% 1000000007
}
return res[n]
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12