Python | Leetcode Python题解之第509题斐波那契数
题目：
题解：
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
q = [[1, 1], [1, 0]]
res = self.matrix_pow(q, n - 1)
return res[0][0]
def matrix_pow(self, a: List[List[int]], n: int) -> List[List[int]]:
ret = [[1, 0], [0, 1]]
while n > 0:
if n & 1:
ret = self.matrix_multiply(ret, a)
n >>= 1
a = self.matrix_multiply(a, a)
return ret
def matrix_multiply(self, 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]
return c