题目描述：
描述查找斐波纳契数列中第 N 个数。所谓的斐波纳契数列是指：前2个数是 0 和 1 。第 i 个数是第 i-1 个数和第i-2 个数的和。斐波纳契数列的前10个数字是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
python代码实现示例：
class Solution:"""@param n: an integer@return: an ineger f(n)"""# 方法3需要用到的函数# def dfs(self, n):#if n <= 2:# return n - 1#return self.dfs(n - 1) + self.dfs(n - 2)# 方法4需要用到的函数 def dfs(self, n, fib):if fib[n] != -1:return fib[n]if n <= 2:fib[n] = n - 1return fib[n]fib[n] = self.dfs(n - 1, fib) + self.dfs(n - 2, fib)return fib[n]def fibonacci(self, n):# write your code here# 方法1: 传统方法# fib = [0, 1, 1]# for i in range(3, n, 1):#fib.append(fib[i - 1] + fib[i - 2])# return fib[n - 1] # 方法2: 方法1传统方法的优化，动态规划的滚动数组思想# 此时时间复杂度不变(没必要存储所有的中间结果)，但是空间复杂度降为O(1)# fib = [0, 1]# for i in range(2, n, 1):#fib[i % 2] = fib[0] + fib[1]# return fib[(n - 1) % 2]# 方法3: 递归法# fibonacci[i] = fibonacci [i - 1] + fibonacci[i - 2]# thisFibonbacci = dfs(i) + dfs(i - 1)# 时间复杂度为O(2^n)，空间复杂度为O(n)（不考虑递归的栈空间占用则为O(1)）# 但是这么做的时间复杂度难以接受，因为有很多被重复计算的数字，# 比如我们在求解fib(10)的时候，会找到fib(9)和fib(8)共两个，# 然后下一层会是fib(8)和fib(7)，fib(7)和fib(6)共四个。# 这是一个呈指数增长的曲线，其底数为2，是稳定超时的代码。# return self.dfs(n) # 方法4: 记忆化搜索, 方法3的优化升级版# 顾名思义，它将计算出的结果存储下来，在计算到指定值的时候，# 先判断这个值是否已经计算过，若没有，才进行计算，# 否则读取已经存储下来的值。这样就把一个指数级复杂度变成了线性复杂度，# 代价是空间复杂度从常数级上升至线性级。result = [-1] * (n + 1)self.dfs(n, result)return result[n]
参考：/problem/366/?_from=collection&fromId=203
