本来以为就是非常简单的一道题，想着递归大法来着，结果n=37时直接超过时间限制了o(╥﹏╥)o

题目

解法

一、动态规划法

• 滚动数组思想

class Solution:
    def fib(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n < 2:
            return n
        p, q, r = 0, 0, 1
        for i in range(2, n + 1):
            p = q
            q = r
            r = (p + q) % MOD
        return r

1
2
3
4
5
6
7
8
9
10
11
12

• 该方法时间复杂度是$O(n)$，但空间复杂度是$O(1)$

二、矩阵法

• 发现$F(n)=F(n-1)+F(n-2)$可以用矩阵表示成
• [ 1 1 1 0 ] [ F ( n ) F ( n − 1 ) ] = [ F ( n ) + F ( n − 1 ) F ( n ) ] = [ F ( n + 1 ) F ( n ) ] \left[
  1110" role="presentation" style="position: relative;">1110$$\begin{array}{ll}1& 1\\ 1& 0\end{array}$$
  \right]\left[
  F(n)F(n−1)" role="presentation" style="position: relative;">F(n)F(n−1)$$\begin{array}{c}F(n)\\ F(n-1)\end{array}$$
  \right]=\left[
  F(n)+F(n−1)F(n)" role="presentation" style="position: relative;">F(n)+F(n−1)F(n)$$\begin{array}{c}F(n)+F(n-1)\\ F(n)\end{array}$$
  \right]=\left[
  F(n+1)F(n)" role="presentation" style="position: relative;">F(n+1)F(n)$$\begin{array}{c}F(n+1)\\ F(n)\end{array}$$
  \right] [11​10​][F(n)F(n−1)​]=[F(n)+F(n−1)F(n)​]=[F(n+1)F(n)​]
• 有 [ F ( n + 1 ) F ( n ) ] = [ 1 1 1 0 ] n [ F ( 1 ) F ( 0 ) ] \left[
  F(n+1)F(n)" role="presentation" style="position: relative;">F(n+1)F(n)$$\begin{array}{c}F(n+1)\\ F(n)\end{array}$$
  \right]=\left[
  1110" role="presentation" style="position: relative;">1110$$\begin{array}{ll}1& 1\\ 1& 0\end{array}$$
  \right]^{n}\left[
  F(1)F(0)" role="presentation" style="position: relative;">F(1)F(0)$$\begin{array}{l}F(1)\\ F(0)\end{array}$$
  \right] [F(n+1)F(n)​]=[11​10​]n[F(1)F(0)​]
• 令 M = [ 1 1 1 0 ] M=\left[
  1110" role="presentation" style="position: relative;">1110$$\begin{array}{ll}1& 1\\ 1& 0\end{array}$$
  \right] M=[11​10​]
• 然后这里的问题就转化成了快速求矩阵乘积，我看官方的方法好像也就是普通的行×列这样的，得自己写个函数
• 函数1：$2\times 2$矩阵乘法
• 函数2：求矩阵的n次方
• 哦哦哦！！我才懂，原来奥秘在算$M^n$的时候，不要一个一个的乘，如果n是偶数，比如说8这种，那我只要计算$M^2\to M^4\to M^8$即可，也就是${\log }_{2}8=3$次即可

代码

class Solution:
    def fib(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n < 2:
            return n

        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            c = [[0, 0], [0, 0]]
            for i in range(2):
                for j in range(2):
                    c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD
            return c

        def matrix_pow(a: List[List[int]], n: int) -> List[List[int]]:
            ret = [[1, 0], [0, 1]]
            while n > 0:
                if n & 1:
                    ret = multiply(ret, a)
                n >>= 1
                a = multiply(a, a)
            return ret

        res = matrix_pow([[1, 1], [1, 0]], n - 1)
        return res[0][0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

-这个 n >>= 1是位运算，之前没见过，开了篇博客一起学习一下（位运算与集合运算）

• 话说这个n&1 = 1也是位运算，就是判断n奇偶性的，等价于n%2 =1
• 时间复杂度是$O(\log n)$,空间复杂度是$O(1)$

三、递归法

• 原理： 把 $f(n)$ 问题的计算拆分成 $f(n-1)$ 和 $f(n-2)$ 两个子问题的计算，并递归，以 $f(0)$ 和 $f(1)$ 为终止条件。
• 缺点： 大量重复的递归计算，例如 $f(n)$和 $f(n-1)$两者向下递归需要 各自计算 $f(n-2)$ 的值。
  • ！！是的！！现在才反应过来，单独算确实有很多重复计算