我认为动态编程是memoization的一个子集 . 这样对吗？
memoization和动态编程有什么区别？
Memoization 是描述优化技术的术语，其中您缓存先前计算的结果，并在再次需要相同的计算时返回缓存的结果 .
Dynamic programming 是一种迭代地解决递归性问题的技术，并且在子问题的计算重叠时适用 .
动态编程通常使用制表来实现，但也可以使用memoization来实现 . 所以你可以看到，没有一个是另一个的"subset" .
一个合理的后续问题是： What is the difference between tabulation (the typical dynamic programming technique) and memoization?
当您使用制表解决动态编程问题时，您可以解决问题“ bottom up ”，即首先解决所有相关的子问题，通常是填写n维表 . 根据表中的结果，然后计算"top" /原始问题的解决方案 .
如果使用memoization来解决问题，可以通过维护已经解决的子问题的映射来实现 . 你先做“ top down " in the sense that you solve the " top”问题（通常会递归以解决子问题） .
从这里一个很好的幻灯片（链接现在已经死了，幻灯片仍然很好）：
如果所有子问题必须至少解决一次，自下而上的动态编程算法通常优于自上而下的memoized算法常数因素没有递归开销和维护表的开销较少有一些常见模式的问题动态编程算法中的表访问可以被利用来进一步减少时间或空间要求如果子问题空间中的一些子问题根本不需要解决，那么memoized解决方案的优点是只解决那些绝对需要的子问题
Additional resources:
维基百科：Memoization，Dynamic Programming
相关SO Q / A：Memoization or Tabulation approach for Dynamic programming
这已被重写为文章here .
动态编程是一种算法范例，通过将其分解为子问题并存储子问题的结果来解决给定的复杂问题，以避免再次计算相同的结果 .
http://www.geeksforgeeks.org/dynamic-programming-set-1/
Memoization是一种简单的方法来跟踪以前解决的解决方案（通常实现为散列键值对，而不是通常基于数组的制表），以便在再次遇到它们时不会重新计算它们 . 它可以用于自下而上或自上而下的方法 .
有关memoization vs tabulation的信息，请参阅this discussion .
因此，动态编程是一种通过解决递归关系/递归并通过制表或记忆存储以前找到的解决方案来解决某些类问题的方法 . 记忆是一种跟踪先前解决的问题的解决方案的方法，并且可以与针对给定输入集具有唯一确定性解决方案的任何函数一起使用 .
动态编程通常称为Memoization！
Memoization是自上而下的技术（通过分解来开始解决给定的问题）和动态编程是一种自下而上的技术（从简单的子问题开始解决，直到给定的问题）
DP通过从基础案例开始查找解决方案并向上运行 . DP解决了所有子问题，因为它是自下而上的
与Memoization不同，它只解决了所需的子问题
DP有可能将指数时蛮力解转换为多项式时间算法 .
DP可能更有效，因为它的迭代
相反，Memoization必须支付由递归引起的（通常很大的）开销 .
更简单的是，Memoization使用自上而下的方法来解决问题，即它从核心（主要）问题开始，然后将其分解为子问题并类似地解决这些子问题 . 在这种方法中，相同的子问题可能多次发生并消耗更多的CPU周期，因此增加了时间复杂度 . 而在动态编程中，相同的子问题将不会被多次解决，但先前的结果将用于优化解决方案 .
（1）从概念上讲，Memoization和DP实际上是一回事 . 因为：考虑DP的定义："overlapping subproblems" "and optimal substructure" . Memoization完全拥有这2个 .
（2）Memoization是DP，堆栈溢出的风险是递归很深 . DP自下而上没有这种风险 .
（3）Memoization需要一个哈希表 . 额外的空间，以及一些查找时间 .
那么回答这个问题：
概念上，（1）意味着它们是同一个东西 .
考虑到（2），如果你真的想要，memoization是DP的一个子集，从某种意义上说，DP可以解决由memo化解决的问题，但是DP可以解决的问题可能无法通过memoization解决（因为它可能堆栈溢出） .
考虑到（3）他们有性能上的微小差异 .
来自维基百科：
Memoization
在计算中，memoization是一种优化技术，主要用于通过函数调用来避免重复计算先前处理的输入的结果来加速计算机程序 .
Dynamic Programming
在数学和计算机科学中，动态规划是一种通过将复杂问题分解为更简单的子问题来解决复杂问题的方法 .
当将问题分解为更小/更简单的子问题时，我们经常遇到相同的子问题，因此我们使用Memoization来保存先前计算的结果，因此我们不需要重复它们 .
动态编程经常遇到使用memoization有意义的情况，但是你可以使用任何一种技术而不必使用另一种技术 .
Memoization和Dynamic Programming都只解决了一次子问题 .
Memoization使用递归并自上而下工作，而动态编程则以相反的方向移动以解决自下而上的问题 .
以下是一个有趣的比喻 -
Top-down - 首先你说我将接管这个世界 . 你会怎么做？你说我会首先接管亚洲 . 你会怎么做？我会先接管印度 . 我将成为德里等首席部长等 .
Bottom-up - 你说我将成为德里的CM . 然后将接管印度，然后是亚洲所有其他国家，最后我将接管世界 .
6 回答
Memoization 是描述优化技术的术语，其中您缓存先前计算的结果，并在再次需要相同的计算时返回缓存的结果 .
Dynamic programming 是一种迭代地解决递归性问题的技术，并且在子问题的计算重叠时适用 .
动态编程通常使用制表来实现，但也可以使用memoization来实现 . 所以你可以看到，没有一个是另一个的"subset" .
一个合理的后续问题是： What is the difference between tabulation (the typical dynamic programming technique) and memoization?
当您使用制表解决动态编程问题时，您可以解决问题“ bottom up ”，即首先解决所有相关的子问题，通常是填写n维表 . 根据表中的结果，然后计算"top" /原始问题的解决方案 .
如果使用memoization来解决问题，可以通过维护已经解决的子问题的映射来实现 . 你先做“ top down " in the sense that you solve the " top”问题（通常会递归以解决子问题） .
从这里一个很好的幻灯片（链接现在已经死了，幻灯片仍然很好）：
Additional resources:
维基百科：Memoization，Dynamic Programming
相关SO Q / A：Memoization or Tabulation approach for Dynamic programming
这已被重写为文章here .
http://www.geeksforgeeks.org/dynamic-programming-set-1/
Memoization是一种简单的方法来跟踪以前解决的解决方案（通常实现为散列键值对，而不是通常基于数组的制表），以便在再次遇到它们时不会重新计算它们 . 它可以用于自下而上或自上而下的方法 .
有关memoization vs tabulation的信息，请参阅this discussion .
因此，动态编程是一种通过解决递归关系/递归并通过制表或记忆存储以前找到的解决方案来解决某些类问题的方法 . 记忆是一种跟踪先前解决的问题的解决方案的方法，并且可以与针对给定输入集具有唯一确定性解决方案的任何函数一起使用 .
动态编程通常称为Memoization！
Memoization是自上而下的技术（通过分解来开始解决给定的问题）和动态编程是一种自下而上的技术（从简单的子问题开始解决，直到给定的问题）
DP通过从基础案例开始查找解决方案并向上运行 . DP解决了所有子问题，因为它是自下而上的
DP有可能将指数时蛮力解转换为多项式时间算法 .
DP可能更有效，因为它的迭代
更简单的是，Memoization使用自上而下的方法来解决问题，即它从核心（主要）问题开始，然后将其分解为子问题并类似地解决这些子问题 . 在这种方法中，相同的子问题可能多次发生并消耗更多的CPU周期，因此增加了时间复杂度 . 而在动态编程中，相同的子问题将不会被多次解决，但先前的结果将用于优化解决方案 .
（1）从概念上讲，Memoization和DP实际上是一回事 . 因为：考虑DP的定义："overlapping subproblems" "and optimal substructure" . Memoization完全拥有这2个 .
（2）Memoization是DP，堆栈溢出的风险是递归很深 . DP自下而上没有这种风险 .
（3）Memoization需要一个哈希表 . 额外的空间，以及一些查找时间 .
那么回答这个问题：
概念上，（1）意味着它们是同一个东西 .
考虑到（2），如果你真的想要，memoization是DP的一个子集，从某种意义上说，DP可以解决由memo化解决的问题，但是DP可以解决的问题可能无法通过memoization解决（因为它可能堆栈溢出） .
考虑到（3）他们有性能上的微小差异 .
来自维基百科：
Memoization
Dynamic Programming
当将问题分解为更小/更简单的子问题时，我们经常遇到相同的子问题，因此我们使用Memoization来保存先前计算的结果，因此我们不需要重复它们 .
动态编程经常遇到使用memoization有意义的情况，但是你可以使用任何一种技术而不必使用另一种技术 .
Memoization和Dynamic Programming都只解决了一次子问题 .
Memoization使用递归并自上而下工作，而动态编程则以相反的方向移动以解决自下而上的问题 .
以下是一个有趣的比喻 -
Top-down - 首先你说我将接管这个世界 . 你会怎么做？你说我会首先接管亚洲 . 你会怎么做？我会先接管印度 . 我将成为德里等首席部长等 .
Bottom-up - 你说我将成为德里的CM . 然后将接管印度，然后是亚洲所有其他国家，最后我将接管世界 .