509. 斐波那契数
https://leetcode-cn.com/problems/fibonacci-number/
使用递归的方法非常简单
func Fibonacci( n int ) int {
if n < 2 {
return n
}
return Fibonacci(n - 1) + Fibonacci(n - 2)
}
如果使用递归会出现重复计算的问题,如下:
所以可以使用一个 Map 来缓存计算结果,但是实际这题考察的是动规,所以 Map 的方式就不展示了
由于斐波那契数存在递推关系,因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系,边界条件为 F(0) 和 F(1)。
由于 F(n) 只和 F(n-1) 与 F(n-2) 有关,因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)。参考:
就是让这三个变量不断的向前递推
func fib(n int) int {
if n < 2 {
return n
}
q,p,r := 0, 0, 1
for i := 2; i <= n; i++ {
q = p
p = r
r = q + p
}
return r
}