剑指 Offer 10- I. 斐波那契数列

题目：剑指 Offer 10- I. 斐波那契数列（E）

解题思路1：

本身是一道很简单的题啊，是当时学习递归时接触到的第一个例子，递归的思想可以，但是当n很大时，重复计算太多，会超时，所以采用动态规划更好一些。一般最初的想法是，设置一个n长的数组把之前的结果都保存下来，这样也可以但是空间复杂度为\(O(N)\)，python的话直接使用两个变量即可，一个存储f(n-1)，一个存储f(n-2)。
时间：\(O(N)\)
空间：\(O(1)\)

class Solution:
    def fib(self, n: int) -> int:
        # if n < 1:    return n
        # else:
        #     sum = [0, 1]
        #     for i in range(2, n + 1):
        #         sum.append(sum[i - 1] + sum[i - 2]) 
        #     return sum[n] % (1000000007)
        a, b = 0, 1
        for i in range(n):
            a, b =  b, (a + b) % 1000000007
        return a % 1000000007

优质解答：矩阵快速幂（参考自官方）

数列递推使用矩阵快速幂以降低时间复杂度。将递推式转化为矩阵形式，如下

\[\begin{bmatrix} F(N)\\ F(N-1) \end{bmatrix} = \begin{bmatrix} 1 && 1 \\ 1 && 0 \end{bmatrix} \begin{bmatrix} F(N-1)\\ F(N-2) \end{bmatrix} \]

推到F(0)和F(1)，则变成

\[\begin{bmatrix} F(N)\\ F(N-1) \end{bmatrix} = \begin{bmatrix} 1 && 1 \\ 1 && 0 \end{bmatrix}^{N-1} \begin{bmatrix} F(1)\\ F(0) \end{bmatrix} \]

所以主要任务就变成求矩阵的N-1次幂，将矩阵A进行两两合并，如果N为偶数，则变成求\((A^2)^{N/2}\)，N为奇数的话，则需要额外在乘一次A，变成求\((A^2)^{N/2}\times A\)，同理在对\(A^2\)进行合并，依次循环，则矩阵求幂就变成只需求\(logN\)次即可。
时间：\(O(logN)\)
空间：\(O(1)\)

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:   return n
        MOD = 10 ** 9 + 7
        def mul(m1, m2):
            res = [[0, 0], [0, 0]]
            for i in range(2):
                for j in range(2):
                    res[i][j] = (m1[i][0]*m2[0][j] + m1[i][1]*m2[1][j]) % MOD
            return res

        def matrix_pow(base, power):
            res = [[1, 0], [0, 1]]
            while power > 0:
                if power & 1:   res = mul(res, base)
                power >>= 1
                base = mul(base, base)
            return res

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

本题解同剑指 Offer 10- II. 青蛙跳台阶问题，初始值不同而已