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

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

当前回答

这是一个记忆和DP从斐波那契数问题写在Java的例子。

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

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
 }
}

2021-09-17 15:04:35

其他回答

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

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

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

为了回答这个问题:

-从概念上讲，(1)意味着它们是一样的东西。

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

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

2014-05-15 22:42:57

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

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

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

请参阅关于记忆和制表的讨论。

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

2014-01-15 18:56:32

在动态规划中，

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