lsc*_*719 0 algorithm dynamic-programming interpretation
这是本书的一段：算法导论，第三版。第336页
“这两种方法产生的算法具有相同的渐近运行时间，但在特殊情况下，自上而下的方法实际上不会递归地检查所有可能的子问题。自下而上的方法通常具有更好的常数因子，因为它的开销更少用于过程调用。”
背景：两种方法是第一种是自上而下+记忆（DP），第二种是自下而上的方法。
我还有一个问题要问你。函数调用的“开销”是否意味着每个函数调用都需要时间？即使我们解决了所有子问题，自上而下也会因为“开销”而花费更多时间？
自下而上的动态规划方法意味着首先解决所有小问题，然后使用它们来找到下一个最小问题的答案，依此类推。因此，例如，如果长度为 n 的问题的解决方案仅取决于长度为 n-1 的问题的答案，则您可以首先放入长度为 0 的所有解决方案，然后迭代地填充长度为 1 的解决方案、2、3 等等，每次都使用您在上一级别已经计算出的答案。它的效率很高，因为这意味着您最终不会两次解决子问题。
自上而下的记忆方法会以另一种方式看待它。如果您想要解决长度为 10 的问题，则可以递归地进行。你注意到它依赖于（比如说）三个长度为 9 的问题，所以你递归地解决它们，然后你知道长度为 10 的答案。但是每当你解决一个子问题时，你都会记住答案，并且每当你需要答案时回答子问题时，您首先查看是否已经解决了它，如果解决了，则返回缓存的答案。
自下而上的方法很好，因为它可以迭代地编写（使用for循环）而不是递归地编写，这意味着在处理大问题时不会耗尽堆栈空间，而且循环也更快。它的缺点是你解决了所有的子问题，并且你可能不需要解决所有的子问题才能解决你想要答案的大问题。
如果您无论如何都需要解决所有子问题，则由于递归开销，自上而下的方法会更慢。但是，如果您要解决的问题只需要解决子问题的一小部分，那么速度会更快，因为它只解决了它需要的问题。
它本质上与急切求值（自下而上）和惰性求值（自上而下）之间的区别相同。