斐波那契数列求解的几种方法

斐波那契数列的定义是f(n + 1) = f(n) + f(n - 1)，生成第 n 项的做法有以下3种。

1. 递归法：

1.1 原理

递归法求解的原理是把 f(n)问题的计算拆分成 f(n-1)和 f(n-2) 两个子问题的计算，并递归，以 f(0)和 f(1)为终止条件。

缺点： 大量重复的递归计算，例如 f(n) 和 f(n - 1)两者向下递归需要 各自计算 f(n - 2)的值。通过下图可以看到这个重复的计算使得递归求解fib的效率并不高。

1.2 代码实现

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(5)) # 5

2. 记忆化递归法（自顶向下的备忘录法）

2.1 原理

在递归法的基础上，新建一个长度为 n 的数组或者字典，用于在递归时存储 f(0)至 f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。
缺点： 记忆化存储需要使用 O(N)的额外空间。

2.2 代码实现

dic = {0: 0, 1: 1}

def fib(n):
    if n in dic: return dic[n]
    else:
        dic[n] = fib(n - 1) + fib(n - 2)
    return dic[n]


print(fib(100))

3. 动态规划

3.1 原理

以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1) 为转移方程。
从计算效率、空间复杂度上看，动态规划是本题的最佳解法。动态规划算法的核心就是记住已经解决过的子问题的解。

3.2 代码实现

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

参考