动态规划有两种等价的实现方法
- 带备忘的自顶向下法。从最大的问题考虑它的子问题。递归形式，过程中会保存每个子问题的解。
- 自底向上法。将子问题按规模排序，按由小到大的顺序进行求解。每个子问题只需求解一次。当我们求解它（第一次遇到时），它的所有前提子问题都已经求解完成。
1. 两种方法有相同的渐近运行时间。
2. 时间差别：在某些情况下，自顶向下没有真正递归考察所有可能的子问题。由于没有频繁的递归函数调用开销，自底向上方法的时间复杂性函数有更小的系数。
3. 如何选择：通常情况下，如果每个子问题至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快，因为自底向上算法没有递归调用的开销。
相反，如果子问题空间中的某些子问题完全不必求解，备忘方法就会体现出优势。
——《算法导论》第三版