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

记忆和动态规划的区别是什么?我认为动态规划是记忆的一个子集。对吗?

127900 次浏览
小开

从维基百科:

记忆有关

在计算中，记忆是一种主要使用的优化技术 通过函数调用来加速计算机程序，避免重复

.

.

.

动态规划

在数学和计算机科学中，动态规划是一种方法 把复杂的问题分解成更简单的问题 子问题。< / p >

当把一个问题分解成更小/更简单的子问题时，我们经常会不止一次遇到相同的子问题——所以我们使用Memoization来保存以前的计算结果，这样我们就不需要重复它们了。

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

小开
最佳答案

编程相关文章。导游:动态规划vs记忆vs制表

记忆和动态规划的区别是什么?< / em >

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

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

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

一个合理的后续问题是:制表(典型的动态编程技术)和记忆之间的区别是什么?

当你用制表法解决一个动态规划问题时，你解决的是“自底向上”问题，即首先解决所有相关的子问题，通常是填满一个__abc1维表。根据表中的结果，然后计算“顶部”/原始问题的解决方案。

如果您使用记忆来解决问题，您可以通过维护已经解决的子问题的映射来实现。你做它“自顶向下”，在某种意义上，你首先解决“顶部”问题(通常递归向下解决子问题)。

来自here的一个很好的幻灯片(链接现在死了，但是幻灯片仍然很好):

    如果所有子问题都必须至少求解一次，自底向上的动态规划算法通常比自顶向下的记忆算法性能好一个常数因子
    • 没有递归的开销和维护表的开销
    • 对于某些问题，动态规划算法中的表访问规则模式可以进一步减少时间或空间需求
      • 李< / ul > < / >
    • 如果子问题空间中的一些子问题根本不需要求解，记忆解的优点是只求解那些肯定需要的子问题

额外的资源:

小开

动态规划通常被称为记忆!

  1. 记忆是一种自顶向下的技术(通过分解来解决给定的问题)，而动态规划是一种自底向上的技术(从微不足道的子问题开始解决，向上到给定的问题)

  2. DP通过从基本情况开始并向上工作来找到解决方案。 DP解决了所有的子问题，因为它是自下而上的

    不像Memoization，它只解决所需的子问题

    李< /引用> < / >

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

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

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

    李< /引用> < / >

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

小开
动态规划是一种求解给定问题的算法范式 将复杂问题分解为子问题并存储结果

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

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

关于记忆和制表，请参阅这个讨论。

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

小开

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

(2)在递归较深的情况下，记忆是DP方法，存在栈溢出风险。DP自下而上没有这种风险。

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

为了回答这个问题:

-从概念上讲，(1)表示它们是相同的东西。

-考虑(2)，如果你真的想，记忆化是DP的一个子集，从某种意义上说，可以通过记忆化解决的问题可以通过DP解决，但是可以通过DP解决的问题可能无法通过记忆化解决(因为它可能会堆栈溢出)。

把(3)考虑在内，它们在性能上有微小的差异。

小开

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

记忆化使用递归并自顶向下工作，而动态规划则相反，自底向上解决问题。

下面是一个有趣的类比

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

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

小开

我想用例子;

问题:

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

每次你可以爬1或2级台阶。有多少不同的方式 你能爬到山顶吗?< / p >

enter image description here

带记忆的递归

通过这种方式，我们在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/

小开

想想两种方法，

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

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

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

注意:

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

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

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

在动态规划中，

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

在记忆,

  • 有些子问题不需要解决。
小开

动态规划 (DP)和记忆有关之间有一些相似之处，在大多数情况下，你可以通过记忆来实现动态编程过程，反之亦然。但它们确实有一些区别，你应该在决定使用哪种方法时查看它们:

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

下面是一个用Java编写的斐波纳契数问题的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
}
}
小开

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


提交答案