题目
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3提示：
0 <= n <= 30
解答
- 递归求解
在递归函数里初始化f(0) = 0,f(1) = 1,对于大于1的函数值，递归调用f(n - 2) + f(n - 1);
class Solution {
public:
int fib(int n) {
if (n == 0) return 0; // f(0)的初始化
if (n == 1) return 1; // f(1)的初始化
return fib(n - 1) + fib(n - 2); // 递归调用
}
};- 迭代求解
C++代码实现如下：
class Solution {
public:
int fib(int n) {
if (n <= 1) return n; // 如果n为0或者1 直接返回它本身
int pre0 = 0, pre1 = 1; // 初始化pre0和pre1
int answer = 0; // 初始化答案
for (int i = 2; i <= n; i++) {
answer = pre0 + pre1; // 答案为f(n-2) + f(n-1)
pre0 = pre1; // pre0的值更新
pre1 = answer; // pre1的值更新
}
return answer; // 计算完毕返回答案
}
};- 矩阵快速幂求解
核心思路是将斐波那契数列的递推式转化为矩阵的乘法，然后使用矩阵快速幂的方法快速计算出矩阵的幂次，进而得到第 n 个斐波那契数。
首先，我们知道斐波那契数列的递推式为：
$F(n) = F(n-1) + F(n-2)，其中 F(0) = 0，F(1) = 1。$
我们可以将这个递推式转化为矩阵的乘法形式：
$ \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} $
根据这个式子，我们可以构造出初始矩阵 base 和单位矩阵 res，然后使用矩阵快速幂的方法快速计算出 base 的 n 次幂，最终得到 res。
最后，我们可以直接返回 res[0][1]，这个值就是第 n 个斐波那契数。
总的来说，这种解法虽然比较高级，但可以在 O(log n) 的时间复杂度内计算出第 n 个斐波那契数，而且不需要使用数组或者递归来存储之前的结果，空间复杂度为 O(1)。
class Solution {
public:
int fib(int n) {
// 如果n小于等于1，直接返回n
if (n <= 1) {
return n;
}
// 定义初始矩阵
vector<vector<int>> base{{1, 1}, {1, 0}};
// 定义单位矩阵
vector<vector<int>> res{{1, 0}, {0, 1}};
// 矩阵快速幂
while (n) {
if (n & 1) {
res = multiply(res, base);
}
base = multiply(base, base);
n >>= 1; // 将变量 n 的二进制表示向右移动一位，并将移位后的结果赋值给 n。相当于n/=2
}
// 返回结果
return res[0][1];
}
// 定义矩阵乘法函数
vector<vector<int>> multiply(const vector<vector<int>>& A, const vector<vector<int>>& B) {
int m = A.size(), n = A[0].size(), l = B[0].size();
vector<vector<int>> C(m, vector<int>(l));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < l; ++j) {
for (int k = 0; k < n; ++k) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
};