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

Question

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

Answer 1

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

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

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

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

---

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

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

如果您使用记忆来解决问题，您可以通过维护已解决的子问题的映射来实现。您按照“自上而下”的方式进行操作，即首先解决“顶部”问题（通常会向下递归以解决子问题）。

一张来自此处<的精彩幻灯片/strike> （链接现已失效，但幻灯片仍然很好）：

• 如果所有子问题必须至少解决一次，则自下而上的动态规划算法通常比自上而下的记忆算法性能好一个常数因子
  • 没有递归开销，维护表的开销更少
  • 对于某些问题，可以利用动态编程算法中的常规表访问模式来进一步减少时间或空间需求
• 如果子问题空间中的某些子问题根本不需要解决，则记忆解决方案的优点是仅解决那些肯定需要的子问题

其他资源：

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

Answer 2

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

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

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

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

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

Answer 3

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

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

下面是一个有趣的类比 -

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

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

Answer 4

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

1. 记忆化是自上而下的技术（通过分解来开始解决给定的问题），而动态编程是自下而上的技术（从琐碎的子问题开始解决，向上解决给定的问题）

2. DP找到解决方案从基本案例开始并向上进行。
   DP 解决了所有子问题，因为它是自下而上的

   <块引用>

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

3. ，DP 具有将指数时间暴力解决方案转换为多项式时间算法的潜力。

4. DP 可能会更高效，因为它是迭代的

   <块引用>

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

   的

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

Answer 5

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

(2) Memoization是DP，由于递归很深，存在堆栈溢出的风险。 DP自下而上不存在这种风险。

(3) Memoization需要哈希表。因此需要额外的空间和一些查找时间。

所以回答这个问题：

-概念上，(1) 意味着它们是同一件事。

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

-考虑到(3)，它们在性能上有微小差异。

Answer 6

来自维基百科：

记忆化

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

动态规划

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

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

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

Answer 7

我想看一个示例；

问题：

您正在爬楼梯。需要n步才能到达顶部。

每次您可以爬 1 或 2 级台阶。有多少种不同的方式
你能爬到山顶吗？

带有记忆化的递归

通过这种方式，我们可以借助 memo 数组来修剪（从树木或灌木中去除多余的材料）递归树并减少递归的大小树直到 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/

Answer 8

只要想到两种方法，

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

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

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

注意：

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

• 由于递归函数调用期间涉及的开销，Memoization 的性能相对较差。

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

Answer 9

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

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

Answer 10

在动态编程中，

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

在记忆中，

• 有些子问题是不需要解决的。

Answer 11

以下是用 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
 }
}

Answer 12

动态编程是对普通递归算法的优化，它考虑输入的所有组合以提供最合适的答案。这种方法有一个缺点，即时间复杂度巨大。通过使用记忆可以提高效率。它将存储子问题的每个输出，并在算法尝试再次解决该子问题时直接给出答案。这可以使算法具有多项式时间复杂度。