斐波纳契数列

╰半橙微兮° 2022-09-05 00:08 98阅读 0赞

**题目描述：**

描述
    查找斐波纳契数列中第 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 - 1
                return 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]

参考：[https://www.lintcode.com/problem/366/?\_from=collection&fromId=203][https_www.lintcode.com_problem_366_from_collection_fromId_203]

[https_www.lintcode.com_problem_366_from_collection_fromId_203]: https://www.lintcode.com/problem/366/?_from=collection&fromId=203