剑指 Offer 10- I. 斐波那契数列（快速幂）

学习快速幂的写法

题目描述

• 方法一：递推
• 方法二：矩阵快速幂

用列表保存斐波那契数列，并在每一步取模，以防溢出

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        F = [0, 1]
        for i in range(2, n+1):
            F.append((F[i-2] + F[i-1]) % (1e9+7))   # 要在这一步就取模，否则最后会溢出导致取模不准
        return int(F[-1])

改进写法，动态规划

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

参考解法，快速幂

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        res = self.matrix_pow([[1, 1], [1, 0]], n-1)    # 求F(n)需要n-1次幂
        return int(res[0][0])

    def matrix_pow(self, matrix, pow):
        """矩阵快速幂"""
        res = [[1, 0], [0, 1]]  # 初始值为单位阵
        while pow > 0:
            # 如果pow为奇数，则将底数乘进res中
            if pow & 1:
                res = self.multiply(res, matrix)
            matrix = self.multiply(matrix, matrix)  # 底数自乘，相当于二分
            pow >>= 1    # 幂二进制向右移一位，等价于pow //= 2
        return res

    def multiply(self, 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]) % (10 ** 9 + 7)
        return res