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

Programming.Guide 的相关文章：Dynamic programming vs memoization vs tabulation

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

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

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

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

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

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

如果您使用记忆化来解决问题，您可以通过维护已经解决的子问题的地图来做到这一点。在您首先解决“顶级”问题（通常会向下递归以解决子问题）的意义上，您可以“自上而下”地执行此操作。

here 的一张好幻灯片（链接现已失效，但幻灯片仍然不错）：

如果所有子问题必须至少解决一次，自下而上的动态规划算法通常优于自上而下的记忆算法一个常数因子 没有递归开销，维护表的开销更少可以利用动态规划算法中的表访问来进一步减少时间或空间需求

其他资源：

维基百科：记忆、动态规划

相关 SO Q/A：动态规划的记忆或制表方法

---

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

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

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

有关记忆与制表的信息，请参见 this discussion。

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

---

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

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

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

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

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

---

动态编程通常称为记忆！

记忆是自上而下的技术（通过分解来解决给定的问题），动态规划是自下而上的技术（从琐碎的子问题开始解决，直到给定问题）DP通过从开始找到解决方案基本情况并向上工作。 DP 解决了所有子问题，因为它是自下而上的，不像记忆化，它只解决所需的子问题 DP 有可能将指数时间蛮力解决方案转换为多项式时间算法。 DP 可能更有效，因为它是迭代的。相反，Memoization 必须支付递归导致的（通常很重要的）开销。

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

---

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

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

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

所以回答这个问题：

-从概念上讲，（1）意味着它们是同一件事。

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

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

---

来自维基百科：

记忆

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

动态规划

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

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

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

---

我想选择example；

问题：

你正在爬楼梯。到达顶部需要 n 步。每次您可以爬 1 或 2 级台阶。你可以通过多少种不同的方式爬上顶峰？

https://i.stack.imgur.com/cZMZ6.png

带记忆的递归

通过这种方式，我们在备忘录数组的帮助下修剪（从树或灌木中去除多余的材料）递归树，并将递归树的大小减小到 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/

---

想了两个办法

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

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

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

笔记：

两者都适用于重叠子问题的问题。

由于递归函数调用期间涉及的开销，记忆对 DP 的执行相对较差。

渐近时间复杂度保持不变。

---

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

记忆化是一种自上而下的方法，在这种方法中，您将一个大问题分解为具有相同属性的较小尺寸的子问题，当尺寸足够小时，您可以通过暴力破解轻松解决它。动态规划是一种自下而上的方法，在此方法中，您首先计算小案例的答案，然后使用它们来构造大案例的答案。

在编码过程中，通常通过递归实现记忆，而动态规划通过迭代进行计算。因此，如果您仔细计算了算法的空间和时间复杂度，使用动态编程风格的实现可以为您提供更好的性能。

确实存在使用记忆化具有优势的情况。动态编程需要计算每一个子问题，因为它不知道将来哪一个有用。但是memoization只计算与原始问题相关的子问题。有时您可能会设计一个理论上具有大量 dp 状态的 DP 算法。但是通过仔细分析，您会发现只会使用可接受的数量。在这种情况下，最好使用 memoization 以避免巨大的执行时间。

---

在动态规划中，

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

表访问的规则模式可用于减少时间或空间需求。

在记忆中，

有些子问题不需要解决。

---

这是一个用 Java 编写的来自 Fibonacci Number 问题的 Memoization 和 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
 }
}

---