斐波那契数列的多种实现方法

斐波那契

0112358
这个数列从第 3 项开始，每一项都等于前两项之和

斐波那契数列递归实现

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}
int main() {
    int a = 0;
    scanf ("%d",&a);
    printf("%d", fib(a));
    return 0;
}

数组实现

对于原问题 f(20) ，就得先计算出子问题 f(19) 和 f(18) ，然后要计算 f(19) ，就要先算出子问题 f(18) 和 f(17) ，以此类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果，递归树不再向下生长了。

对于递归树，算法低效的原因就是因为存在大量重复计算，比如 f(18) 被计算了两次，而且以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。并且还不止 f(18) 这一个节点被重复计算，所以这个算法及其低效。

因为存在多个重复的子元素，

• 时间复杂度为 $O({\frac{1+\sqrt{5}}{n}}^{2})=O(2^n)$
• 空间复杂度为 $O(n)$

耗时的原因是重复计算，所以可以通过构造一个「备忘录」来实现简化，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；以后每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    int memo[N + 1] = {0};
    // 进行带备忘录的递归
    return helper(memo, N);
}
//输入-开辟空间-进入辅助函数
int helper(vector<int> &memo, int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

子问题个数，即图中节点的总数，由于这个新的算法不存在冗余计算，子问题就是 $f(1), f(2), f(3) \cdots f(20)$，数量和输入规模 $n = 20$ 成正比，所以子问题个数为 $n$。

解决一个子问题的时间，同上，没有什么循环，时间为 $O(1)$ 。

所以，本算法的时间复杂度是 $O(n)$ 。比起暴力算法，是降维打击。

dp 数组的迭代解法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表

int fib(int N) {
    int dp[N + 1] = {0};
    // base case
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}

还是用数组进行存储的方法，改变遍历方向而已，上面的就叫做动态规划

当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O (1):

int fib(int n) {
    if (n == 2 || n == 1) 
        return 1;
    int fir = 1, sec = 1;
    for (int i = 3; i <= n; i++) {
        int thr = fir + sec;
        fir = sec;
        sec = thr;
    }
    return sec;
}