记忆化和动态编程的区别是什么？

Question

记忆化和动态编程的区别是什么？我认为动态编程是记忆化的一个子集。是对的吗？

Answer 1

动态编程是一种算法范式，它通过将给定的复杂问题分解为子问题并存储子问题的结果来解决给定的复杂问题，以避免再次计算相同的结果。

http://www.geeksforgeeks.org/dynamic-programming-set-1/

Memoization是一种跟踪以前求解的解决方案的简单方法(通常实现为散列键值对，而不是通常基于数组的制表)，以便在再次遇到它们时不会重新计算它们。它可以在自底向上或自上而下的方法中使用。

参见this discussion关于memoization与tabulation的比较。

因此，动态编程是一种通过求解递归关系/递归并通过表格或记忆存储先前找到的解决方案来解决某些类问题的方法。记忆是一种跟踪以前解决问题的解决方案的方法，可以与任何对给定输入集具有唯一确定性解决方案的函数一起使用。

Answer 2

Memoization和Dynamic Programming都只解决一个子问题一次。

Memoization使用递归并自上而下地工作，而动态编程则相反，自下而上地解决问题。

下面是一个有趣的类比：

自上而下的-首先你说我会接管世界。你会怎么做呢？你说我会先接管亚洲。你会怎么做呢？我会先接管印度。我将成为德里的首席部长，等等。

自下而上的-你说我将成为德里的CM。然后将接管印度，然后是亚洲所有其他国家，最后我将接管世界。

Answer 3

动态编程通常被称为记忆化！

1. 记忆是自上而下的技术(通过分解来开始解决给定的问题)，而动态编程是一种自下而上的技术(从微不足道的子问题开始解决，直到给定的问题)
2. DP通过从基本情况开始查找解决方案，并向上查找解决方案。DP解决了所有子问题，因为它是自下而上的

与Memoization不同，Memoization只解决所需的子问题

1. DP具有将指数时间暴力解转换为多项式时间算法的潜力。
2. DP可能会更高效，因为它的迭代

相反，记忆化必须为递归带来的(通常是相当大的)开销买单。

更简单地说，Memoization使用自上而下的方法来解决问题，即从核心(主)问题开始，然后将其分解为子问题，并以类似的方式解决这些子问题。在这种方法中，相同的子问题可能会多次出现，消耗更多的CPU周期，从而增加时间复杂度。然而，在动态规划中，同一个子问题不会被多次求解，而是利用先前的结果对解进行优化。