动态规划问题(1) 之 斐波那契数列

动态规划问题的学习思路总结

1、由斐波那契数列引入重叠子问题（斐波那契数列严格来说不是动态规划问题）

1）暴力递归

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

时间复杂度为：O(2^n)

画出递归树：

分析：因为计算fib(20)，就需要计算fib(19)和fib(18)，计算fib(19)有需要计算fib(18)和fib(17)，最后到fib(2)和fib(1)。很明显算法低效的原因是存在大量的重复计算。这就引入了动态规划问题的第一个性质：重叠子问题。

2）用带备忘录的递归解法

因为重复计算造成了效率的低下，那我们考虑定义一个备忘录，每次计算完子问题的答案后先别急着返回，而是先记录到备忘录中再返回；每次遇到一个子问题先去备忘录中查看是否已经有记录，如果发现之前已经计算过这个问题，直接把答案拿来使用即可，不用再花时间去计算。这里使用vector 数组维护备忘录。

int fib(int n)
{
    if(n < 1)
        return 0;
    vector<int> memo(n+1, 0); //备忘录先初始化为0
    return helper(memo, n); //从下标1开始使用，下标0不使用，直到下标n。共n个元素
}
​
int helper(vector<int> & memo, int n)
{
    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];
}

再次画出递归树：

我们可以发现，相比暴力递归，备忘录的递归对之前的递归树进行了剪枝操作，极大减少了子问题个数。

递归算法的时间复杂度：

子问题个数×解决一个子问题需要的时间，子问题个数即为图中节点的总数，即数量与输入规模成正比，所以子问题个数为O(n)，解决一个子问题的时间为O(1)，所以此算法的时间复杂度为O(n)。效率已经和迭代的动态规划解法一样了。此算法我们是自顶向下的分解问题规模，直到最底层的fib(1)和fib(2)，然后再从下往上逐层返回答案。而自底向上则正好相反，是从最底层的fib(1)和fib(2)向上推，直到fib(20)，这就是动态规划的思路。

3）用 dp 数组迭代解法

我们将解法2中的备忘录独立出来成为一张表，在这张dp表上完成自底向上的推算，即可解决问题。

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

因为我们计算一个状态只需要记录前两个记录即可，而不需要存储所有的状态，所以还可以进一步优化空间复杂度：

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

画图帮助理解：

这里引出 状态转移方程这个名词，实际上就是描述问题结构的数学形式：

                                                      

很容易可以发现 状态转移方程 直接代表着暴力解法。

动态规划问题最困难的就是写出状态转移方程，即暴力解法，优化方法无非是用 备忘录或者DP table。

 

本文是参考labuladong公众号的文章自己记录的学习笔记，仅供大家参考和自己再次复习，有兴趣的同学可以关注公众号labuladong进一步学习。有很多优秀的文章可以学习。