英文:
Is Memoization considered Dynamic Programming?
问题
我对动态规划和记忆化之间的区别感到困惑。我一直以为它们是完全相同的东西，只是不同的表述，但如果情况不是这样的，是否有人可以澄清一下它们的含义？每次我点击不同的博客时，谷歌都会给我不同的答案。
英文:
I'm confused about what the difference between dynamic programming and memoization is. I always thought they were the exact same thing, just different words, but if this isn't the case, could somebody please clarify what they mean?
Google gives me different answers every time I click on a different blog.
答案1
得分: 3
相关的 Programming.Guide 文章: 动态规划 vs. 记忆化 vs. 填表法
> 记忆化和动态规划有什么区别？
记忆化 是描述一种优化技术的术语，其中你会缓存先前计算过的结果，并在再次需要相同计算时返回缓存的结果。
<!-- 使用记忆化的 Fibonacci 函数会使用一个缓存来存储先前计算过的结果。随着结果变得可用，缓存会被懒惰地填充。 -->
动态规划 是一种解决递归性质问题的技术，通过迭代解决，并且适用于子问题的计算重叠的情况。
<!-- 使用动态规划的 Fibonacci 函数会类似地工作，但是“缓存”将是一个预先分配的数组，函数会急切地计算 cache[0]、cache[1]，直到计算出包含最终结果的 cache[n] 为止。-->
动态规划通常使用填表法来实现，但也可以使用记忆化来实现。所以，可以看出它们之间都不是彼此的“子集”。
一个合理的后续问题是：填表法（典型的动态规划技术）和记忆化之间的区别是什么？
当你使用填表法来解决动态规划问题时，你从底部开始解决问题，即首先解决所有相关的子问题，通常是通过填充一个 n 维表格来实现的。基于表格中的结果，然后计算出“顶部”/原始问题的解决方案。
如果你使用记忆化来解决问题，你会通过维护已经解决的子问题的映射来实现。你会以“自顶向下”的方式解决问题，即首先解决“顶部”问题（通常会递归地解决子问题）。
来自<strike>这里</strike>的一个好的幻灯片（链接已失效，但幻灯片仍然可用）：
> - 如果所有子问题至少都必须被解决一次，自底向上的动态规划算法通常比自顶向下的记忆化算法性能更好，差距是一个常数因子
> - 递归没有开销，并且维护表格的开销较小
> - 对于一些问题，动态规划算法中表格访问的正常模式可以被利用以进一步减少时间或空间需求
> - 如果某些子问题在子问题空间中根本不需要被解决，记忆化解决方案的优势在于只解决那些明确需要的子问题
其他资源：
- 维基百科：记忆化，动态规划
- 相关的栈溢出问答：https://stackoverflow.com/questions/12042356/memoization-or-tabulation-approach-for-dynamic-programming
来源：https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming
英文:
Relevant article on Programming.Guide: Dynamic programming vs memoization vs tabulation
> What is difference between memoization and dynamic programming?
Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.
<!-- A fibonacci function using memoization would use a cache of previously computed result. The cache would be populated lazily as results become available. -->
Dynamic programming is a technique for solving problems of recursive nature, iteratively and is applicable when the computations of the subproblems overlap.
<!-- A fibonacci function using dynamic programming would work similarly, but the "cache" would be a preallocated array, and the function would compute cache[0], cache[1] ... eagerly until cache[n] is computed which contains the end result.-->
Dynamic programming is typically implemented using tabulation, but can also be implemented using memoization. So as you can see, neither one is a "subset" of the other.
A reasonable follow-up question is: What is the difference between tabulation (the typical dynamic programming technique) and memoization?
When you solve a dynamic programming problem using tabulation you solve the problem "bottom up", i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the "top" / original problem is then computed.
If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems. You do it "top down" in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).
A good slide from <strike>here</strike> (link is now dead, slide is still good though):
> - If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor
> - No overhead for recursion and less overhead for maintaining table
> - There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further
> - If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required
Additional resources:
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论