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(n) = F(n - 1) + F(n - 2)$

由于斐波那契数存在递推关系，因此可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。

由于 F(n) 只和 F(n-1) 与 F(n-2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 O(1)。参考：

https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

就是让这三个变量不断的向前递推

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
}