algorithm - book interpretation, about DP (你能换句话解释一下这段文字吗？)

Question

这是本书的一段:Introduction to Algorithms, 3rd Edition。第336页

"These two approaches yield algorithms with the same asymptotic running time, expect in unusual circumstances where the top-down approach does not actually recurse to examine all possible subproblems. The bottom-up approach often has much better constant factors, since it has less overhead for procedure calls."

上下文:两种方法第一种是自上而下+记忆化(DP)，第二种是自下而上的方法。

---

我还有一个问题要问你。函数调用的“开销”是否意味着每个函数调用都需要时间？即使我们解决了所有子问题，自顶向下也会因为“开销”而花费更多时间？

Answer 1

动态规划的自下而上方法意味着首先解决所有小问题，然后使用它们找到下一个最小问题的答案，依此类推。因此，例如，如果长度为 n 的问题的解决方案仅取决于长度为 n-1 的问题的答案，您可能会首先输入长度为 0 的所有解决方案，然后您将迭代地填写长度为 1 的解决方案, 2, 3, 依此类推，每次都使用您在上一级别已经计算出的答案。它是高效的，因为它意味着您最终不会两次解决一个子问题。

采用内存方法的自上而下会以另一种方式看待它。如果你想要解决长度为 10 的问题，那么你可以递归地这样做。你注意到它依赖于(比方说)三个长度为 9 的问题，所以你递归地解决它们，然后你知道长度为 10 的答案。但是每当你解决一个子问题时，你记得answer，当你需要一个子问题的答案时，你首先看看你是否已经解决了它，如果你已经解决了，你返回缓存的答案。

自下而上方法的好处在于它可以迭代编写(使用 for 循环)而不是递归，这意味着您不会在大问题和循环上耗尽堆栈空间也更快。它的缺点是你解决了所有的子问题，你可能不需要解决所有的子问题来解决你想要答案的大问题。

如果您需要解决所有子问题，自上而下的方法会比较慢，因为递归开销。但如果您要解决的问题只需要解决子问题的一小部分，速度会更快，因为它只解决了它需要的问题。

本质上和eager evaluation(自下而上)和lazy evaluation(自上而下)的区别是一样的。