Fibonacci Number
斐波那契数列从 F(0) = 0 和 F(1) = 1 开始，之后的每个数都是前两个数的和：F(n) = F(n-1) + F(n-2)。这个数列从 0，1，1，2，3，5，8，13 开始。你的函数接收 n，并返回 F(n)。
函数
- ninteger
- 从 0 开始计数的斐波那契数列中的位置
- 返回值integer
- 斐波那契数 F(n)
约束条件
0 ≤ n ≤ 45- 答案可以用有符号 32 位整数表示：
F(45) = 1134903170。
示例
- 输入
- n = 4
- 输出
- 3
- 解释
- 从起始值开始递增：
F(2) = 1 + 0 = 1、F(3) = 1 + 1 = 2，以及F(4) = 2 + 1 = 3。
- 输入
- n = 10
- 输出
- 55
- 解释
- 从索引 0 开始，序列依次为 0、1、1、2、3、5、8、13、21、34、55。索引 10 处的数字是
34 + 21 = 55。
进阶
你能在 F(n) 的 O(log n) 时间内计算吗？
提示
逐个打开提示，每个都会多透露一点。
用递归定义手动计算
F(5)。你最终会重复计算哪些值？每个斐波那契数只需要它前面的两个数。如果按递增顺序计算，需要某个值时，这个值就已经算出来了。
从
0和1开始。重复n-1次：把你手中的两个数字相加，然后舍弃较早的那个，保留它们的和。
题解
这个定义本身就是一个递归函数，按递归方式编写也能得到正确答案，但需要指数级时间，因为两个调用会重复完成对方的工作。动态规划从底向上计算，每个数只计算一次。每个数只需要前面的两个数，所以两个变量就够了。
直接从定义理解递归
结果正确，但无法在最大的测试中运行完毕
思路
翻译这个定义：return fib(n-1) + fib(n-2)，其中 fib(0) = 0，fib(1) = 1。每条调用链都会以基本情况结束，因此答案是正确的。
这些调用会重复计算。fib(5) 会运行两次 fib(3)、三次 fib(2) 和五次 fib(1)，总共调用 15 次。一般来说，F(n) 需要调用 2 × F(n+1) - 1 次；当 n = 45 时，大约需要 3.7 × 10^9 次调用。调用次数按 1.618^n 的速度增长，通常写作 O(2^n)。调用栈深度为 n 层，因此空间复杂度为 O(n)。
算法
- 如果
n是0或1，就返回n。 - 否则，对
n-1和n-2调用该函数。 - 返回这两个结果的和。
def fib(n):
if n < 2:
return n # F(0) = 0, F(1) = 1
return fib(n - 1) + fib(n - 2)从下往上填充表格
思路
递归之所以慢，是因为它会遗忘。每个数第一次计算出来时，就把它记下来，这样每个数只需要一次加法。从左到右填表：当你到达 f[i] 时，它需要的两个值都已经在表里了。当 n = 10 时，表中的数是 0、1、1、2、3、5、8、13、21、34、55。
这需要 n-1 次加法，时间复杂度为 O(n)，并占用 n + 1 个位置，空间复杂度为 O(n)。n = 45 时只需 44 次加法，而不是调用数十亿次。
算法
- 如果
n是0或1，返回n。 - 创建一个包含
n + 1个数字的表，并设置f[0] = 0和f[1] = 1。 - 对于从 2 到
n的i，设置f[i] = f[i-1] + f[i-2]。 - 返回
f[n]。
def fib(n):
if n < 2:
return n
f = [0] * (n + 1) # f[i] will hold F(i)
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]只保留最后两个数字
思路
填充 f[i] 时只会读取 f[i-1] 和 f[i-2]，所以更早的所有位置都没有用。保留两个变量：prev，表示前两步的数字；curr，表示前一步的数字。对于 n = 4，这对数值会从（0，1）变为（1，1）、（1，2）和（2，3），而 curr = 3 就是答案。
工作量相同，都是 n-1 次加法，时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 如果
n是0或1，则返回n。 - 将
prev = 0和curr = 1设为初始值。 - 重复
n-1次：计算next = prev + curr，然后将prev = curr和curr = next设为新值。 - 返回
curr。
def fib(n):
if n < 2:
return n
prev, curr = 0, 1 # F(0) and F(1)
for _ in range(n - 1):
prev, curr = curr, prev + curr
return curr
易错点和边界情况
- 提交朴素的递归实现。它是正确的，但当
n = 45时会进行数十亿次函数调用。 - 从 1、1 开始这个数列。这里
F(0) = 0，所以F(10)是 55，而不是 89。 - 表格版本没有处理较小
n的保护条件。当n = 0时，表格只有一个位置，因此写入f[1]会越界。当n < 2时返回n。 - 以错误的顺序更新这对变量。先执行
prev = curr，再执行curr = prev + curr，会导致curr每一步都翻倍，因此n = 4时会返回 8。先计算next，或者使用同时赋值。
常见问题3
递归 Fibonacci 函数的时间复杂度是多少？
朴素递归会进行 2 × F(n+1) - 1 次调用，这个数量的增长速度约为 1.618^n，通常写作 O(2^n)。把每个结果存储一次，无论是存进表中还是两个变量中，都能将复杂度降到 O(n)。
为什么递归版斐波那契数列只使用 O(n) 空间？
一次只有一条调用链位于栈上，最深的调用链从 n 开始，依次到 n-1，再到 1。调用返回时会释放它的栈帧，因此栈中最多只会有 n 个栈帧，尽管调用总数呈指数级增长。
如何用动态规划求解斐波那契数列？
按 n 的递增顺序计算这些值，并将每个值存储在一张从下往上填充的表中。或者保留递归函数，并缓存它的结果，这称为记忆化。无论哪种方式，每个值都只计算一次，因此工作量为 O(n)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def fib(n):
# 在这里编写代码测试 #1
测试 #2
参数
n = 4
预期输出
3