斐波那契数列

斐波那契数列

---

<div align = 'right'>作者：hackett</div>

<div align = 'right'>微信公众号：加班猿</div>

---

问题结构描述的数学形式：

image-20201115220851688

一、暴力递归解法

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

解析：代码虽然简洁，但是效率十分低下，算法的时间复杂度为O(),指数级别，爆炸（通过递归树可以看出这个解法还存在重叠子问题）

二、备忘录递归解法

用一个一维数组（哈希表、字典）充当这个「备忘录」

int fib(int n)
{
    if(n < 1)
        return 0;
    vector<int> memo(n+1,0);    //初始化备忘录为0
    return calc(memo,n);        //初始化最简情况
}
int calc(vector<int>& memo,int n)
{
    if(n == 1 || n == 2)
        return 1;
    //计算
    if(memo[n] != 0)
        return memo[n];
    memo[n] = calc(memo,n-1) + calc(memo,n-2);
    return memo[n];
}

解析：每次算出某个⼦问题的答案后别急着返回，先记到「备忘录」⾥再返回；每次遇到⼀个⼦问题先去「备忘录」⾥查 ，⼀查，如果发现之前已经解决过这个问题了，直接把答案拿出来⽤，不要再 耗时去计算了

算法的时间复杂度为O(n)，比起暴力解法，降了一个维度，「⾃顶向下」形式

三、数组的迭代解法

有了第二的「备忘录」启发，我们将它独立出来成为一张表，在这边表上完成「⾃底向上」

int fib(int n)
{
    vector<int> db(n+1,0);  //初始化
    db[1] = 1;
    db[2] = 1;
    for(int i = 3 ; i < n ; i++)
        db[i] = db[i-1] + db[i-2]
    return db[n];
}

上述的操作return fib(n -1) + fib(n - 2)， db[i] = db[i-1] + db[i-2]，都是围绕这个⽅程式的不同表现形式。可⻅列出「状态转移⽅程」的重要性，它是 解决问题的核⼼。所以，进一步优化把空间复杂度降为 O(1)

int fib(int n)
{
    if(n == 1 || n == 2)
        return 1;
    int prev = 1,curr = 1;
    for(int i = 3 , i < n ; i++)
    {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

解析：动态规划问题最困难的就是写出状态转移⽅程，即上面的暴力解。

根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么⻓的⼀个 db 表来存储所有的状态，只要想办法存储之前的两个状态就⾏了

如果你觉得文章还不错，记得"点赞关注"

关注我的微信公众号【 加班猿 】可以获取更多内容