©2020-2024 ioDraw All rights reserved
题目
概述：写一个函数，输入 n ，求斐波那契数列的第 n 项。斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模
1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
输入：n = 2 输出：1 输入：n = 5 输出：5
方法一：递归
思路：会超时，不详细展开了
# 递归 class Solution: def fib(self, n: int) -> int: if n == 0: return 0 if n ==
1: return 1 return (self.fib(n - 1) + self.fib(n - 2)) % (10 ** 9 + 7)
方法二：动态规划
思路：动态规划的状态转移方程即为上述递推关系，边界条件为 F(0) 和 F(1)。由于 F(n) 只和 F(n−1) 与 F(n−2)
有关，因此可以使用「滚动数组思想」来优化空间复杂度。
# 动态规划 class Solution: def fib(self, n: int) -> int: mod = 10 ** 9 + 7 if n <
2: return n x_1, x_2, x_3 = 0, 1, 1 for i in range(2, n + 1): x_3 = (x_1 + x_2)
% mod x_1, x_2 = x_2, x_3 return x_3 class Solution: def fib(self, n: int) ->
int: x_1, x_2 = 0, 1 for i in range(n): x_1, x_2 = x_2, (x_1 + x_2) return x_1
% (10 ** 9 + 7)
方法三：矩阵快速幂
思路：我们能快速计算矩阵 M 的 n 次幂，就可以得到 F(n) 的值。
# 矩阵快速幂 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]
总结
只有我一个人想知道这个取模的作用吗？