题目

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0,  F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

解答

方法一 迭代

根据递推公式直接循环模拟计算过程。

其实也是动态规划,只不过用三个变量滚动代替了状态数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int fib(int n) {
if(n < 2){
return n;
}
int a=0, b=1, c=0;
while(n > 1){
c = (a + b) % (int)(1e9 + 7);
a = b;
b = c;
n--;
}
return c;
}
};

复杂度

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)

方法二 记忆化递归

递归解决子问题。但要注意的是递归时会产生大量重复计算,可能会超时,所以使用一个记忆数组避免重复计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int cache[101];
int fib(int n) {
if(n < 2){
return n;
}
if(cache[n] != 0) return cache[n];
cache[n] = (fib(n-1) + fib(n-2)) % (int)(1e9 + 7);
return cache[n];
}
};

复杂度

  • 时间复杂度 O(n)
  • 空间复杂度 O(n)

方法三 矩阵快速幂

根据数的递推关系可以构建矩阵的递推关系:

易得:

因此只需要计算矩阵 M 的 n-1 次幂即可快速得到 F(n)。计算矩阵 n 次幂时可以使用矩阵快速幂的方法加速计算。

快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在 O(log n) 的时间内计算 $a^n$ 的小技巧。

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
const int MOD = 1000000007;

int fib(int n) {
if (n < 2) {
return n;
}
vector<vector<long>> q{{1, 1}, {1, 0}};
vector<vector<long>> res = pow(q, n - 1);
return res[0][0];
}

// 矩阵快速幂
vector<vector<long>> pow(vector<vector<long>>& a, int n) {
vector<vector<long>> ret{{1, 0}, {0, 1}};
while (n > 0) {
if (n & 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}

// 矩阵乘法
vector<vector<long>> multiply(vector<vector<long>>& a, vector<vector<long>>& b) {
vector<vector<long>> c{{0, 0}, {0, 0}};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
}
}
return c;
}
};

复杂度

  • 时间复杂度 O(log n)
  • 空间复杂度 O(1):只用了固定常数大小的二维数组