动态规划自顶向下和自底向上
动态规划中的自顶向下和自底向上是指两种不同的求解动态规划问题的方法：
1. 自顶向下：这种方法不考虑整个图结构，直接从要求的状态开始展开式子，如果式子中的某个状态的值还不清楚，就递归的从这个状态展开。递归结束后式子中的状态都被对应的值替换了，所求状态自然也就清楚了。
2. 自底向上：这种方法已经知道了所有递归边界，把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程，从所有递归边界出发，当一个状态被所有可能的下层状态更新后，就用这个状态去更新后面的状态。直到所求的状态被彻底更新完成为止。
需要注意的是，这两种方法的实现方式不同，自顶向下是递归的，依赖于子问题优化函数的结果，只有子问题完全求出，也就是子问题的递归返回结果，原问题才能求解。而自底向上是迭代的，巧妙的安排求解顺序，从最小的子问题开始，自下而上求解。每次求新的问题时，子问题的解已经计算出来了。
版权声明：
本文内容由互联网用户自发贡献，该文观点仅代表作者本人。如发现本站有涉嫌抄袭侵权/违法违规的内容，请联系删除。
