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