Neovim-如何使用编辑器的神

斐波那契数列介绍

$f(0) = 1$

$f(1) = 1$

$f(n) = f(n - 1) + f(n - 2), n \in Z, n \geqslant 2$

注意:

• 有些题目会把第0项定义成0.
• 爬楼梯问题, 爬0阶楼梯的方案数是1.

滚动变量

时间复杂度是$O(n)$, 空间复杂度是$O(1)$

int fib(int n)
{
    int a = 1, b = 1;
  while (n --)
  {
    int c = a + b;
    a = b, b = c;
  }
  return a;
}

快速幂

https://www.acwing.com/problem/content/19/

https://leetcode.cn/problems/climbing-stairs/description/

快速幂可以在$O(logn)$的时间复杂度内求解斐波那契数列的第$n$项.

定义向量$X_n = [a_n, a_{n - 1}]$, 那么$X_1 = [a_1, a_0]$

可以找到矩阵

$$A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}$$

使得$X_n = X_{n - 1} \times A$

那么$X_n = X_1 \times A^{n-1}$

那么, 求斐波那契数列的问题就转化成了求矩阵$A^{n-1}$的问题, 这个问题可以用快速幂求解.

注意, 这个方法第0项需要单独判断, 因为要保证$n - 1 \geqslant 0$.

class Solution {
public:
    void mul(int a[2][2], int b[2][2], int c[2][2])
    {
        int tmp[2][2] = {{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i ++)
            for (int j = 0; j < 2; j ++)
                for (int k = 0; k < 2; k ++)
                    tmp[i][j] += a[i][k] * b[k][j];

        for (int i = 0; i < 2; i ++)
            for (int j = 0; j < 2; j ++)
                c[i][j] = tmp[i][j];
    }
    int Fibonacci(int n) {

        if (n == 0) return 0;
        /* 定义初始向量[a1, a0] */
        int x[2] = {1, 0};
        /* 定义矩阵A */
        int A[2][2] = {{1, 1}, {1, 0}};
        /* 要计算A的n - 1次幂 */
        int k = n - 1;

        int res[2][2] = {{1, 0}, {0, 1}};

        /* 快速幂 */
        while (k)
        {
            /* mul的意思是把res * A的值放到res中 */
            if (k & 1) mul(res, A, res);
            mul(A, A, A);
            k >>= 1;
        }
        /* 计算x和A^{n-1}的乘积的第一项 */
        return x[0] * res[0][0] + x[1] * res[1][0];
    }
};