什么是记忆化和动态规划的区别？

Question

什么是记忆化和动态规划的区别？

dynamic-programmingterminologydifferencememoization

358

记忆化和动态规划有什么区别？我认为动态规划是记忆化的一个子集。这是否正确？

- Sanghyun Lee

动态规划与备忘录算法 - burnabyRails

12个回答

53

动态规划是一种算法范式，它将一个复杂问题分解成子问题，并存储子问题的结果以避免重复计算相同的结果。

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

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

请参见有关记忆化与制表法的此讨论。

因此，动态规划是一种通过解决递归关系/递归并通过制表法或记忆化存储先前发现的解决方案来解决某些类别问题的方法。记忆化是一种方法，用于跟踪先前解决的问题的解决方案，并可用于具有给定输入集的唯一确定性解决方案的任何函数。

- Tom M

42

记忆化搜索和动态规划都只解决了每个子问题一次。

记忆化搜索使用递归，自上而下处理问题，而动态规划则相反地自底向上解决问题。

以下是一个有趣的比喻：

自上而下 - 首先你说我要征服世界。你会如何做到呢？你说我会先征服亚洲。那么你如何做到呢？我会先征服印度。我将成为德里的首席部长等等。

自底向上 - 你说我会成为德里的首席部长。然后我们会接管印度，然后亚洲其他国家，最后我们会征服全世界。

- Priyanshu Agarwal

5

喜欢这个类比！ - Cataster

我也是，这实际上是一条适用于生活的好建议。先专攻一项，然后看看它会为你打开哪些门。 - Sridhar Sarnobat

这里有另一个用孩子数数和Gazini忘记/记住的有趣类比：https://youtu.be/p4VRynhZYIE - Om Sao

备忘录化并不是“使用递归”。它可以用来提高递归函数的效率，但也可以在任何函数被多次调用的情况下使用，而不一定是递归函数。 - undefined

19

动态规划通常被称为记忆化！

记忆化是自顶向下的技术(通过拆解问题来解决给定问题)，而动态规划是自底向上的技术(从微不足道的子问题开始解决，直至解决给定问题)
动态规划通过从基本情况开始工作并向上工作来找到解决方案。 DP解决所有子问题，因为它是自底向上的。

与记忆化不同，后者仅解决所需的子问题。
DP有潜力将指数时间暴力解决方案转变为多项式时间算法。
DP可能更加高效，因为它是迭代的。

相反，记忆化必须支付递归产生的（通常很大的）开销。

更简单来说，记忆化使用自顶向下的方法解决问题，即从核心(主)问题开始，然后将其分解为子问题并以类似的方式解决这些子问题。在此方法中，相同的子问题可能会多次出现并占用更多的CPU周期，从而增加时间复杂度。而在动态规划中，相同的子问题不会被多次解决，但是先前的结果将被用来优化解决方案。

- Farah Nazifa

13

(1) Memoization（记忆化）和DP（动态规划），在概念上是相同的。因为：考虑DP的定义：“重叠子问题”和“最优子结构”。Memoization完全具备这两个条件。

(2) Memoization（记忆化）是DP的一种，但如果递归深度过大，则有栈溢出的风险。DP自底向上不会存在此风险。

(3) Memoization（记忆化）需要使用哈希表，因此需要额外的空间和一定的查找时间。

所以回答问题：

-从概念上讲，（1）意味着它们是相同的东西。

-考虑到（2），如果你真的想要，记忆化是DP的一个子集，解决了可以用记忆化解决的问题都可以使用DP解决，但是用DP处理的问题可能无法用记忆化解决（因为它可能会发生栈溢出）。

-考虑到（3），它们在性能上有细微差异。

- PoweredByRice

11

来源于维基百科：

记忆化

在计算机领域中，记忆化是一种优化技术，主要用于加速计算机程序，通过避免函数调用重复处理已处理过的输入结果。

动态规划

在数学和计算机科学中，动态规划是一种通过将复杂问题分解成较简单子问题来解决问题的方法。

当将一个问题分解成更小/简单的子问题时，我们经常会多次遇到相同的子问题 - 因此使用记忆化来保存先前计算的结果，以便不必重复计算。

动态规划通常会遇到使用记忆化技术有意义的情况，但您可以仅使用其中一种技术而不必使用另一种。

- yurib

OP在我回答后编辑了问题。原始问题询问两者之间的区别。 - yurib

8

我想给出一个例子：

问题:

你正在攀爬一座楼梯。需要n个台阶才能到达顶部。

每次你可以选择爬1步或2步。你可以用多少种不同的方式爬上楼顶？

记忆化递归

通过memo数组帮助我们修剪（从树木或灌木中去除多余的材料）递归树，将递归树的大小减小到n。

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

动态规划

我们可以将这个问题分解为子问题，且它包含最优子结构性质，即其最优解可以有效地由其子问题的最优解构建而成。我们可以使用动态规划来解决这个问题。

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

本示例取自https://leetcode.com/problems/climbing-stairs/

- Teoman shipahi

4

思考两种方式：

将大问题分解为小的子问题 - 自上而下的方法。
从最小的子问题开始，逐步解决大问题 - 自下而上的方法。

在记忆化搜索中，我们采用(1.)的方法，将每次函数调用的结果保存在缓存中并从缓存中调用。由于涉及到递归调用，因此它稍微费一些时间。

在动态规划中，我们采用(2.)的方法，通过使用保存在表中的数据来解决子问题，自下而上地维护一个表，通常称为dp-table。

注意:

两种方式都适用于具有重叠子问题的问题。
相对于记忆化搜索，动态规划表现较好，因为递归函数调用时涉及的开销较小。
渐进时间复杂度保持不变。

- Neel Alex

3

动态规划（DP）和记忆化之间存在一些相似之处，大多数情况下，您可以通过记忆化实现动态规划过程，反之亦然。但它们确实有一些区别，在决定使用哪种方法时应进行检查：

记忆化是自顶向下的方法，在此期间，您将一个大问题分解为具有相同属性的较小子问题，当大小足够小时，您可以通过暴力计算轻松解决它。动态规划是自底向上的方法，首先计算小案例的答案，然后使用它们构建大案例的答案。
在编码过程中，通常采用递归实现记忆化，而动态规划则通过迭代进行计算。因此，如果您已经仔细计算了算法的时间和空间复杂度，则使用动态规划风格的实现可以提供更好的性能。
确实存在使用记忆化的优势的情况。动态规划需要计算每个子问题，因为它不知道哪个子问题将在未来有用。但是记忆化只计算与原始问题相关的子问题。有时，您可能会设计具有理论上巨大数量的 dp 状态的 DP 算法。但是通过仔细分析，您会发现只使用了可接受数量的状态。在这种情况下，最好使用记忆化以避免执行时间过长。

- starling

1

在动态规划中，

没有递归的开销，维护表格的开销也较小。
可以利用表格访问的规律来减少时间或空间的需求。

在记忆化中，

某些子问题不需要解决。

- Pasan Yasara

我认为这就像是对数表和计算器之间的区别。一个可以进行“即时”计算，而另一个只是查找结果，因此速度非常快（并且已经在过去积极地预先计算，因为我们知道它对某些人很有用）。 - Sridhar Sarnobat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aioobe · Accepted Answer

编程指南上相关文章: 动态规划 vs 记忆化搜索 vs 表格法。

“记忆化搜索”和“动态规划”有什么区别？

“记忆化搜索”是一种优化技术，其中您可以缓存先前计算的结果，并在需要再次进行相同计算时返回缓存的结果。

“动态规划”是一种递归问题的求解技术，通常使用“表格法”实现，适用于子问题的计算重叠的情况。

“动态规划”通常使用“表格法”实现，但也可以使用“记忆化搜索”。因此可以看出，它们并不是彼此的“子集”。

一个合理的后续问题是：制表法（典型的动态规划技术）和记忆化之间有什么区别？ 使用制表法解决动态规划问题时，您通过首先解决所有相关子问题来“自下而上”解决问题，通常是通过填充n维表格来实现的。根据表中的结果，然后计算出“顶部”/原始问题的解决方案。

如果您使用记忆化来解决该问题，则通过维护已解决子问题的映射来完成，以“自上而下”的方式进行，因为您首先解决“顶部”问题（通常递归下去解决子问题）。这里（链接现在已失效，但幻灯片仍然很好）提供了一张好的幻灯片：

如果必须至少解决一次所有子问题，则自下而上的动态编程算法通常比自上而下的记忆化算法快一定的倍数
- 没有递归开销，维护表的开销较小
- 对于某些问题，可以利用动态规划算法中表访问的常规模式来进一步减少时间或空间要求
如果在子问题空间中有些子问题根本不需要解决，则记忆化解决方案具有仅解决确实需要的子问题的优势

其他资源：

维基百科：记忆化, 动态规划
相关 SO 问答: 动态规划的记忆化或表格法