套路，让你更好地理解动态规划

很多人会觉得算法很难，特别是对于初学者来说，这个其实我是认同的，包括现在我仍然觉得算法数据结构还有很多需要去探索的东西，如何去运用到现实的开发中也是个难题。多年前我开始学习算法的时候，也有很多东西没办法一下子就学会，后来慢慢地接触到一些套路，有时候，一个有用的套路，可以让你茅塞顿开，是打开前进之门的金钥匙。今天我们来介绍下动态规划算法实现的两个套路----自底向上与自顶向下。

如果还不懂动态规划算法，后面有链接。

我们通过一个最常见的动态规划的题目来讲这个。

斐波那契数列，大家都非常熟悉，f[i] = f[i - 1] f[i - 2]。f[1] = f[0] = 1, 输入n, 输出f[n].

我们先来讲动态规划算法这两个算法的实现套路。

自底向上：

自底向上就是已经知道了所有递归边界，把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程，从所有递归边界出发，当一个状态被所有可能的下层状态更新后，就用这个状态去更新后面的状态。直到所求的状态被彻底更新完成为止。

这段话，说成人话就是：从初始已知的状态出发，向外拓展，最后到达目标状态。

我们用自底向上实现这个题目就是：

我们再来讲另外一个套路，自顶向下。

自顶向下就是不考虑整个图结构，直接从要求的状态开始展开式子，如果式子中的某个状态的值还不清楚，就递归的从这个状态展开。递归结束后式子中的状态都被对应的值替换了，所求状态自然也就清楚了。

说成人话就是：从最终状态开始，找到可以到达当前状态的状态，如果该状态还没处理，就先处理该状态。

自顶向下通常使用递归实现，自顶向下的动态规划通常又有另外一个形象名字，叫做“记忆化搜索”。因为我们会去保存那个状态。

上面的题目如果使用自顶向下的套路，实现为：

我们要求f[n]直接就从f[n]开始寻找答案。

总结：

自顶向下，自底向上，只是动态规划实现的套路而已。复杂度并没有多大的变化。（事实上大多时候用自顶向下复杂度会更低，因为可以过滤掉更多无用的状态；不过自底向上可以避免爆栈问题，而且实现往往实现更为简单。）选择哪一个还是要根据题目而定，没有哪一个绝对地好。我们再来回顾一下这两个的特点。

自底向上：从初始已知的状态出发，向外拓展，最后到达目标状态。

自顶向下：从最终状态开始，找到可以到达当前状态的状态，如果该状态还没处理，就先处理该状态。

前面我们讲的几个都是用自底向上解决的。欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh），后面我们会继续讲到自顶向下的动态规划的算法。

扩展阅读：

动态规划入门《动态规划算法入门，需要搞懂这5个问题》。