从斐波那契数列开始了解什么是动态规划

首先看斐波那契数列的问题

首先我们来看最简单的斐波那契数列的问题：

拿到这个问题，直观上非常简单，几乎是一个递归就能搞定的事，所以我们有：

def f1(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return f1(n - 1) + f1(n - 2)

我们分别计算了f1(20)和f1(40)，时间大致分别为：0.01s和44s。
可见差距非常之大，这分明是一个指数级的复杂度。

我们分析一下为什么会这么慢，看一个计算斐波那契数列的图：

在这个图中我们能看到大量的重复计算，比如求解f4计算了两次f2，求解f5的时候又计算了很多次f2，那我们能解决这个问题吗？

记忆化搜索

解决递归中的重复解，通常使用记忆化搜索的方式，我们看代码：

memo = [-1] * (n + 1)
def f2(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if memo[n] == -1:
        memo[n] = f2(n - 1) + f2(n - 2)
    return memo[n]

其实就是把我们求解过的东西记下来，此时会发现，很快就能够得到结果，测试100以内基本上是毫秒级出结果。

动态规划

刚刚讲的两种，都是递归的解法，都是自上而下的思考问题，我们先考虑f5，然后再考虑f4和f3，一层层往下。
而动态规划是一种自下而上的思考方式。

以同样的题目，对于动态规划来说，它的思考方式是：

def f3(n):
    memo = [-1] * (n + 1)
    for i in range(0, n + 1):
        if i == 0:
            memo[i] = 0
        elif i == 1:
            memo[i] = 1
        else:
            memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]

可以看到，它是从n=0开始思考问题的。

维基百科上给的定义是：将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。

动态规划和递归、记忆化搜索的不同

最大的不同自然是思考的方向上，当然除此以外，记忆化搜索毕竟还是递归调用，有递归就有栈消耗。