Question source

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

三种解法：递归，递归 + 数组存储 与 动态规划

1. 递归

传统解法，好写，但会超时。

Complexity

  • 时间复杂度：O(2^n)
  • 空间复杂度：递归栈的空间
图一：递归图解

显然，计算fib(6)，从图片中可以看到，f(3)重复计算了3次，f(4)重复计算了2次，可想而知，越往上，那么重复计算的次数会越多。

Code

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n): 
        if n >= 2:
            return self.Fibonacci(n-1) + self.Fibonacci(n-2) 
             
        elif n == 0 or n==1:
            return n

2. 记忆法递归

新建数组保存中间值，避免重复计算。

Complexity

  • 时间复杂度：O（n）
  • 空间复杂度：O（n）和递归栈的空间

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int fib(int n) {
        int [] arr = new int[n + 1];
        for (int i = 0; i < arr.length;i++) {
            arr[i] = -1;
        }
        return fibWithArray(n, arr);
    }
    public int fibWithArray(int n,int [] arr) {
        if (n < 2) {
            return n;
        }
        if (arr[n] == -1) {
            arr[n] = (fibWithArray(n-1, arr) + fibWithArray(n-2, arr)) % 1000000007;
        }
        return  arr[n];
    }
}

3. 动态规划

拿一个list列表去存下来已经计算好的f(n)，然后进行列表操作，核心思想就是动态规划。

Complexity

  • 时间复杂度：O（n）
  • 空间复杂度：O（n）和递归栈的空间

Code

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*- 
class Solution:
    def Fibonacci(self, n):
        # write code here
        res = [0,1]
        while len(res) <= n:
            res.append(res[-1]+res[-2])
        return res[n]

优化： 不拿一个list列表去存下来已经计算好的f(n)，而用sum,b,a存储中间变量，减少空间复杂度。

Complexity

  • 时间复杂度：O（n）
  • 空间复杂度：O(1)

Code

1
2
3
4
5
6
7
8
9
10
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: return n
        
        sum,t1,t2 = 0,0,1
        for i in range(1,n):
            sum = (t1 + t2)% 1000000007
            t1 = t2
            t2 = sum
        return sum

⚠️ 1. 1000000007 是10位的最小质数，上面的代码并没有问题，只是数字太大溢出了，需要将计算结果 % 1000000007才能保证得出的结果在int 范围中；

  1. 优化方法在输出结果表现看，和未优化不相上下。

参考

https://blog.nowcoder.net/n/c0d4560b127c4c549e3420884b18ba51