高频面试算法题之斐波那契数

读前福利，送大家一些电子书

斐波那契数

509. 斐波那契数

问题描述

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

示例：

输入：2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

分析问题

我们把整个求解过程分为 n 个阶段，每个阶段去求解数列对应项的值。我们在解决当前问题时，也就是求解该对应项的值的时候，会依赖过去的状态，也就是前面几项的值来计算。比如我们在求解 F(6) 的时候，我们需要用到 F(5) 和 F(4) 这两项。

我们来定义一个数组，来记录每项的状态。这个数组也叫做状态转移矩阵。按照斐波那契数列的定义：

F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2) (n>=2)

从中可以知道 F(n) 的值只与它的前两个状态有关。所以我们只要知道它的前两个状态，就可以求出 F(n)。

1. 初始化值 F(0)=0，F(1)=1，我们直接放入数组中。
2. 要想计算F(2)，我们需要知道 F(0) 和 F(1)，因为上一步已经放入数组中，我们直接拿来用就好了，然后把 F(2) 的结果放入数组中。
3. 要想计算F(3)，我们需要知道 F(2) 和 F(1)，因为 F(2) 和 F(1) 已经存在数组里了，我们直接拿来用就好了，然后把 F(3) 的结果放入数组中。
4. …

依此类推，直到计算到 n 为止。整个状态转移矩阵就计算好了。如下图所示。我们以求解 F(5) 为例。

代码如下所示：

def fibs(n):
     if n<2:
          return n
     dp=[0 for _ in range(n+1)]
     dp[0]=0
     dp[1]=1
     for i in range(2,n+1):
          dp[i]=dp[i-1]+dp[i-2]
     return dp[n]
print(fibs(6))