题解 | #斐波那契数列#的Python解法

1. 解题思路一

这道题如果很熟悉斐波拉契数列的定义（即 f(n)=f(n-1)+f(n−2)） ，那么用递归是最易懂的方法。但是递归的时间复杂度达到O( $图片说明$ )，且空间复杂度也有O(n)；所以这并不是最优解。
因此，很多朋友提到了动态规划的解法，可是很少有朋友解释为何可以用动态规划来解决？，下面，掌柜就从这里展开。

1.1 回顾动态规划

首先什么样的问题适合用动态规划解决？
符合“一个模型三个特征”的问题。
那么问题又来了，什么是“一个模型，三个特征”？
“一个模型”👉：指多阶段决策最优解模型；
“三个特征”👉：分别是最优子结构、无后效性和重复子问题。

1.2 动态规划图解本题

先来看看它为何更适合动态规划 的方法。首先我们看这个递归树：
（为了方便解释，这里选取 f(0) 到 f(6) 进行解说）
“动态规划”的解题思路：
- 状态转移表法（回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码）；
- 状态转移方程法（找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码）。
  此题我们采用第二种思路，即状态转移方程法。
由于最优子结构上面我们已经分析了，所以直接进入写状态转移方程这一步，直接上图：

同理可以得到f(3)时的状态转移过程：
图片说明
同理可以得到后面的转移过程：

所以递推的转移方程就可以得到为：a, b = b, a + b (初始a 和b 分别为 0， 1）。

3. 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #斐波拉契数的边界条件： F(0)=0 和 F(1)=1
        if n < 2:
            return n
        else:
            a, b = 0, 1
            for i in range(n-1):
                a, b = b, a + b        #状态转移方程，每次滚动更新数组

            return b

4. 复杂度分析

时间复杂度：O(n) (根据状态转移方程和边界条件，可以得到时间复杂度 O(n))
空间复杂度：O(n) (同上)

----------------------------------------我是解法二的分割线------------------------------------------------

5. 解法二

5.1 思路

由于F(n) 只和F(n−1) 与F(n−2) 有关，因此只需要初始化三个整数变量 sum, a, b ，利用辅助变量sum 使 a, b两数字交替更新即可。
这样做就节省了动态规划列表的空间，因此空间复杂度降至 O(1)。

5.1 核心代码：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #斐波拉契数列的边界条件
        if n < 2:
            return n
        #初始化三个整形变量
        a, b, sum = 0, 0, 1
        for i in range(2, n + 1):  
            #利用辅助变量sum 使 a, b两数字交替更新即可
            a, b = b, sum
            sum = a + b

        return sum

5.2 复杂度分析

时间复杂度：O(n) (根据状态转移方程和边界条件，可以得到时间复杂度 O(n))
空间复杂度：O(1) (见思路)