dynamic-programming - 记忆化和动态编程有什么区别？

Question

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

score 465 · Accepted Answer

Programming.Guide 上的相关文章：动态编程 vs 记忆化 vs 制表

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

记忆是一个描述优化技术的术语，您可以在其中缓存先前计算的结果，并在再次需要相同的计算时返回缓存的结果。

动态规划是一种迭代解决递归性质问题的技术，适用于子问题的计算重叠时。

动态编程通常使用制表实现，但也可以使用记忆化来实现。如您所见，两者都不是另一个的“子集”。

一个合理的后续问题是：制表（典型的动态编程技术）和记忆化之间有什么区别？

当您使用制表解决动态规划问题时，您会“自下而上”地解决问题，即首先解决所有相关的子问题，通常是通过填写一个n维表。根据表中的结果，然后计算“顶部”/原始问题的解决方案。

如果您使用记忆化来解决问题，您可以通过维护已经解决的子问题的地图来做到这一点。你是“自上而下”的，因为你首先解决了“顶级”问题（通常会向下递归解决子问题）。

一张从~~这里开始~~的好幻灯片（链接现在已经死了，但幻灯片仍然很好）：

如果所有子问题必须至少解决一次，自下而上的动态规划算法通常优于自上而下的记忆算法一个常数因子

没有递归开销，维护表开销更少

对于某些问题，可以利用动态规划算法中的常规表访问模式来进一步减少时间或空间需求

如果子问题空间中的某些子问题根本不需要解决，则记忆解决方案的优点是只解决那些绝对需要的子问题

其他资源：

维基百科：记忆，动态规划
相关 SO Q/A：动态规划的记忆或制表方法

score 51 · Accepted Answer

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

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

记忆是一种跟踪先前解决的解决方案的简单方法（通常实现为哈希键值对，而不是通常基于数组的制表），以便在再次遇到它们时不会重新计算它们。它可以用于自下而上或自上而下的方法。

请参阅有关记忆化与制表的讨论。

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

score 31 · Accepted Answer

记忆化和动态规划都只解决单个子问题一次。

记忆使用递归并自上而下工作，而动态编程则以相反的方向移动，自下而上解决问题。

下面是一个有趣的类比——

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

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

score 18 · Accepted Answer

动态编程通常称为记忆！

记忆是自上而下的技术（通过分解来解决给定的问题），动态规划是一种自下而上的技术（从琐碎的子问题开始解决，直到给定问题）
DP 通过从基本案例开始并向上工作来找到解决方案。DP解决了所有的子问题，因为它是自下而上的

不像记忆，它只解决了需要的子问题
DP 具有将指数时间蛮力解决方案转换为多项式时间算法的潜力。
DP 可能更有效，因为它是迭代的

相反，Memoization 必须支付由于递归而产生的（通常很重要的）开销。

更简单地说，记忆化使用自上而下的方法来解决问题，即它从核心（主要）问题开始，然后将其分解为子问题并类似地解决这些子问题。在这种方法中，相同的子问题可能会发生多次并消耗更多的 CPU 周期，因此会增加时间复杂度。而在动态编程中，相同的子问题不会被多次解决，但先前的结果将用于优化解决方案。

score 12 · Accepted Answer

(1) Memoization 和 DP，从概念上讲，实际上是一回事。因为：考虑DP的定义：“重叠子问题”“和最优子结构”。Memoization 完全具备这 2 个。

(2) Memoization 是 DP 有堆栈溢出的风险是递归很深。DP 自下而上没有这种风险。

(3) 记忆化需要一个哈希表。所以额外的空间和一些查找时间。

所以回答这个问题：

-从概念上讲，(1) 表示它们是同一事物。

- 考虑到（2），如果你真的想要，memoization 是 DP 的一个子集，从某种意义上说，可以通过 memoization 解决的问题将可以通过 DP 解决，但是可以通过 DP 解决的问题可能无法通过 memoization 解决（因为它可能堆栈溢出）。

- 考虑到（3），它们的性能差异很小。

score 10 · Accepted Answer

来自维基百科：

记忆

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

动态规划

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

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

动态编程经常遇到使用记忆化有意义的情况，但您可以使用任何一种技术而不必使用另一种。

score 7 · Accepted Answer

我想举个例子；

问题：

你正在爬楼梯。到达顶部需要 n 步。

每次您可以爬 1 或 2 级台阶。你可以通过多少种不同的方式爬上顶峰？

带记忆的递归

通过这种方式，我们在备忘录数组的帮助下修剪（从树或灌木中去除多余的材料）递归树，并将递归树的大小减小到 nn。

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/

score 4 · Accepted Answer

想了两个办法

我们将较大的问题分解为较小的子问题 - 自上而下的方法。
我们从最小的子问题开始，到达更大的问题——自下而上的方法。

在Memoization中，我们使用 (1.) 将每个函数调用保存在缓存中并从那里回调。它有点昂贵，因为它涉及递归调用。

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

笔记：

两者都适用于重叠子问题的问题。
由于递归函数调用期间涉及的开销，记忆对 DP 的执行相对较差。
渐近时间复杂度保持不变。

score 3 · Accepted Answer

动态编程(DP) 和记忆化之间有一些相似之处，在大多数情况下，您可以通过记忆化来实现动态编程过程，反之亦然。但是它们确实存在一些差异，您在决定使用哪种方法时应该检查它们：

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

score 1 · Accepted Answer

在动态规划中，

没有递归开销，维护表的开销更少。
表访问的规则模式可用于减少时间或空间需求。

在记忆中，

有些子问题不需要解决。

score 0 · Accepted Answer

这是一个用 Java 编写的斐波那契数问题的记忆和 DP 示例。

这里的动态编程不涉及递归，因为它不受执行堆栈的限制，结果更快并且可以计算更高的值。

public class Solution {

 public static long fibonacciMemoization(int i) {
    return fibonacciMemoization(i, new long[i + 1]);
 }

 public static long fibonacciMemoization(int i, long[] memo) {
    if (i <= 1) {
        return 1;
    }
    if (memo[i] != 0) {
        return memo[i];
    }
    long val = fibonacciMemoization(i - 1, memo) + fibonacciMemoization(i - 2, memo);
    memo[i] = val;
    return val;
 }

 public static long fibonacciDynamicPrograming(int i) {
    if (i <= 1) {
        return i;
    }
    long[] memo = new long[i + 1];
    memo[0] = 1;
    memo[1] = 1;
    memo[2] = 2;
    for (int j = 3; j <= i; j++) {
        memo[j] = memo[j - 1] + memo[j - 2];
    }
    return memo[i];
 }

 public static void main(String[] args) {
    System.out.println("Fibonacci with Dynamic Programing");
    System.out.println(fibonacciDynamicPrograming(10));
    System.out.println(fibonacciDynamicPrograming(1_000_000));

    System.out.println("Fibonacci with Memoization");
    System.out.println(fibonacciMemoization(10));
    System.out.println(fibonacciMemoization(1_000_000)); //stackoverflow exception
 }
}

dynamic-programming - 记忆化和动态编程有什么区别？

11 回答 11

Related

Reference