[C++知识库]斐波拉契数列完全解析(C++)

斐波拉契数列的定义如下：

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

1. 暴力递归

int fib(int n)
{
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    return fib(n-1) + fib(n-2);
}

我们画一个图来演示一下fib(5)的计算过程：

可以发现有很多重复计算，所以这种方式效率极低。

2. 带记忆数组的递归
   我们可以把f(1),f(2),f(3)这种子问题的返回值急着返回，先存到记忆数组里，在下次需要求解的时候直接先去记忆数组里查询就好了。

int fib(int n)
{
    std::vector<int> memo(n + 1, 0);
    if (n == 0)
    {
        memo[n] = 0;
    }
    if (n == 1 || n == 2)
    {
        memo[n] = 1;
    }
    if (n > 2)
    {
        if (memo[n] != 0)
            return memo[n];
        memo[n] = fib2(n - 1) + fib2(n - 2);
    }
    return memo[n];
}

通过递归我们“自顶向下”从一个规模较大的原问题，向下逐渐分解规模，最后直到分解成f(0),f(1),f(2)这样的base case，然后再逐层返回结果，这就是“自顶向下”。

但是我们也知道，f(3)是由f(1)和f(2)的结果推导出来的，也就是最简单的最小规模的问题往上推，最后是能够推出我们想要的较大规模的答案，这个就是动态规划的思想，通过循环迭代取代递归。

3. 循环迭代

int fib3(int n)
{
    std::vector<int> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

4. 聊聊动态规划
   动态规划的三个要素：1.存在重叠子问题。2.具备最优子结构。3.状态转移方程。

那么斐波拉契数列的状态转移方程就是： $$f(n)=1,n=1,2;f(n?1)+f(n?2),n>2;$$

5. 优化空间复杂度
   从状态转移方程可以看出，f(n)只依赖之前的两个状态，因此我们只需要存储之前的两个状态，而不需要存储所有的中间状态。

int fib4(int n)
{
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    int pre = 1;    //前一个状态
    int prepre = 1; //再前一个状态
    for (int i = 3; i <= n; i++)
    {
        int sum = pre + prepre;
        prepre = pre;   //更新
        pre = sum;
    }
    return pre; //此时pre就是最后一个sum  也就是应该返回的状态
}

完整代码：

#include <iostream>
#include <vector>

int fib1(int n)
{
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    return fib1(n - 1) + fib1(n - 2);
}

int fib2(int n)
{
    std::vector<int> memo(n + 1, 0);
    if (n == 0)
    {
        memo[n] = 0;
    }
    if (n == 1 || n == 2)
    {
        memo[n] = 1;
    }
    if (n > 2)
    {
        if (memo[n] != 0)
            return memo[n];
        memo[n] = fib2(n - 1) + fib2(n - 2);
    }
    return memo[n];
}

int fib3(int n)
{
    std::vector<int> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int fib4(int n)
{
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;
    int pre = 1;
    int prepre = 1;
    for (int i = 3; i <= n; i++)
    {
        int sum = pre + prepre;
        prepre = pre;
        pre = sum;
    }
    return pre;
}

int main()
{
    //std::cout << "Hello World!\n";
    std::cout << fib1(30) << std::endl;
    std::cout << fib2(30) << std::endl;
    std::cout << fib3(30) << std::endl;
    std::cout << fib4(30) << std::endl;
    return 0;
}