记忆和dynamic编程有什么区别？
我认为dynamic编程是记忆的一个子集。 这样对吗？
记忆和dynamic编程有什么区别？
记忆是一个描述优化技术的术语，用于caching先前计算的结果，并在需要再次进行相同的计算时返回caching的结果。
dynamic规划是一种recursion求解问题的技术，适用于子问题计算重叠的情况。
dynamic编程通常使用制表来实现，但也可以使用记忆来实现。 正如你所看到的，没有一个是另一个的“子集”。
一个合理的后续问题是： 列表（典型的dynamic编程技术）和记忆之间有什么区别？
当你使用列表解决dynamic规划问题时，你可以解决“ 自下而上 ”的问题，即首先解决所有相关的子问题，通常是填充一个n维表。 根据表中的结果，然后计算“最高”/原始问题的解决scheme。
如果你使用memoization来解决问题，你可以通过维护已经解决的子问题的地图来完成。 你首先解决“顶级”问题（通常是recursion解决子问题）的意义上，它是“自上而下”的。
从这里的一个很好的幻灯片（链接现在已经死了，幻灯片仍然不错）：
- 如果所有的子问题都必须至less解决一次，那么自下而上的dynamic规划algorithm通常比自顶向下的memoizedalgorithm优于常数因子
- 没有用于recursion的开销和维护表的更less的开销
- 有一些问题可以利用dynamic规划algorithm中的表格访问规则模式来进一步减less时间或空间要求
- 如果子问题空间中的某些子问题根本不需要解决，则该解决scheme的优点是只能解决那些绝对需要的子问题
其他资源：
- 记忆 ， dynamic规划
- 相关SO Q / A： dynamic规划的记忆或制表方法
这已被改写为一篇文章在这里 。
dynamic规划是一种algorithm范式，通过将其分解为子问题来解决给定的复杂问题，并存储子问题的结果以避免再次计算相同的结果。
http://www.geeksforgeeks.org/dynamic-programming-set-1/
Memoization是跟踪以前解决的解决scheme（通常实现为散列键值对，而不是通常基于数组的列表）的简单方法，以便在再遇到它们时不会重新计算。 它可以用于自下而上或自上而下的方法。
请参阅关于记忆与制表的讨论。
用于dynamic编程的记忆或列表方法
所以dynamic规划是一种解决某些types的问题的方法，通过解决recursion关系/recursion和通过列表或记忆来存储以前find的解决scheme。 记忆是一种跟踪以前解决的问题的解决scheme，可以用于具有给定input集合的唯一确定性解决scheme的任何函数。
dynamic编程通常被称为Memoization！
-
记忆是自上而下的技术（通过分解来解决给定的问题），dynamic规划是自下而上的技术（从平凡的子问题开始解决，直到给定的问题）
-
DP从基本情况开始寻找解决scheme并向上工作。 DP解决了所有的子问题，因为它是自下而上的
不像Memoization，它只解决了所需的子问题
-
DP有可能将指数时间蛮力解转化为多项式时间algorithm。
-
DP可能效率更高，因为它是迭代的
相反，Memoization必须支付由recursion引起的（经常是重要的）开销。
为了更简单，Memoization使用自上而下的方法来解决问题，即从核心（主要）问题开始，然后将其分解成子问题并类似地解决这些子问题。 在这种方法中，同样的子问题可能会发生多次，消耗更多的CPU周期，从而增加了时间复杂度。 而在dynamic编程中，相同的子问题不会被多次解决，而是使用前面的结果来优化解决scheme。
（1）在概念上 ，记忆和DP是真的一回事。 因为：考虑DP的定义：“重叠子问题”和“最优子结构”。 备忘录完全拥有这2个。
（2）记忆是DP与堆栈溢出的风险是recursion很深。 DP自下而上没有这个风险。
（3）记忆需要一个哈希表。 所以额外的空间和一些查找时间。
所以要回答这个问题：
– 从概念上讲 ，（1）意味着它们是相同的东西。
– 考虑到（2），如果你真的想，记忆是DP的一个子集，从某种意义上讲，记忆可以解决的问题可以被DP解决，但是DP可以解决的问题可能不能通过记忆解决（因为它可能会堆栈溢出）。
考虑到（3），它们在性能上有微小的差别。
从维基百科：
记忆化
在计算中，记忆是一种优化技术，主要用于通过函数调用来避免重复计算以前处理的input的结果来加速计算机程序。
dynamic编程
在math和计算机科学中，dynamic规划是将复杂问题分解成更简单的子问题的一种方法。
当把一个问题分解成更小更简单的子问题时，我们经常会遇到同样的子问题 – 所以我们使用Memoization来保存之前的计算结果，所以我们不需要重复它们。
dynamic编程通常会遇到使用记忆的情况，但是您可以使用其中一种技术，而不必使用其他技术。
