记忆和动态编程之间有什么区别? [英] What is the difference between memoization and dynamic programming?

问题描述

记忆化和动态编程之间有什么区别?我认为动态编程是记忆的一个子集.是吗?

What is the difference between memoization and dynamic programming? I think dynamic programming is a subset of memoization. Is it right?

推荐答案

与Programming.Guide有关的文章:

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.

动态编程是一种迭代解决递归性质问题的技术，适用于子问题的计算重叠的情况.

Dynamic programming is a technique for solving problems of recursive nature, iteratively and is applicable when the computations of the subproblems overlap.

动态编程通常 使用列表来实现，但是也可以使用备忘录来实现.因此，您可以看到，任何一个都不是另一个的子集".

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?

使用制表法解决动态编程问题时，可以解决"自下而上"问题，即先解决所有相关子问题，通常先填写 n -维表.根据表中的结果，然后计算顶部"/原始问题的解决方案.

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 here (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

其他资源:

• 维基百科:备忘录，动态编程的记忆化或列表化方法

• Wikipedia: Memoization, Dynamic Programming
• Related SO Q/A: Memoization or Tabulation approach for Dynamic programming

这篇关于记忆和动态编程之间有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！