牛客网在线编程专题《剑指offer-面试题9》斐波那契数列

我的个人微信公众号：Microstrong

微信公众号ID：MicrostrongAI

微信公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容，分享在学习过程中的读书笔记！期待您的关注，欢迎一起学习交流进步！

知乎主页：https://www.zhihu.com/people/MicrostrongAI/activities

Github：https://github.com/Microstrong0305

个人博客：https://blog.csdn.net/program_developer

题目链接：

https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tqId=11160&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

解题思路：

（1）递归解法

此解法时间复杂度和空间复杂度都很大，时间复杂度为O()、空间复杂度为O(N)。

递归代码解法正确，但是在牛客网上这道题不能AC，原因是时间复杂度太高。

给出递归解法代码：

class Solution: def Fibonacci(self, n): # write code here if n == 0: return 0 if n == 1: return 1 return self.Fibonacci(n - 1) + self.Fibonacci(n - 2) so = Solution() print(so.Fibonacci(7))

（2）动态规划解法

方法一：时间复杂度为O(N)，空间复杂度为O(N)

已经AC的Java代码：

import java.util.Arrays; public class fibonacci { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(Fibonacci(7)); } public static int Fibonacci(int n) { if(n == 0) return 0; else if(n == 1 || n == 2) return 1; else { int[] memo = new int[n+1]; Arrays.fill(memo, -1); memo[0] = 0; memo[1] = 1; memo[2] = 1; for(int i=3; i<=n; i++) { if(memo[i] == -1) memo[i] = memo[i-1] + memo[i-2]; } return memo[n]; } } }

已经AC的Python代码：

# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): # write code here res = [0 for i in range(n + 1)] if n == 0: return 0 if n == 1: return 1 if n >= 2: res[0] = 0 res[1] = 1 for i in range(2, n + 1): res[i] = res[i - 1] + res[i - 2] return res[n]

方法二：时间复杂度为O(N)，空间复杂度为O(3)

# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): if n == 0: return 0 if n == 1: return 1 if n >= 2: a = 0 b = 1 c = 0 for i in range(2, n + 1): c = a + b a = b b = c return c

（3）斐波那契的通项公式法，时间复杂度为O(1)

f(n) = closed - form solution

 已经AC的代码：

# -*- coding:utf-8 -*- import math class Solution: def Fibonacci(self, n): # write code here sqrtFive = math.sqrt(5) return sqrtFive / 5 * (math.pow(((1 + sqrtFive) / 2), n) - math.pow(((1 - sqrtFive) / 2), n))

思考题：斐波那契数的通项公式怎么得来的？

提示：转换成矩阵的连乘的形式，矩阵连乘可以简化（Matrix Decomposion）。fibonacci number closed form derivation。