memoization和动态编程有什么区别？

Question

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

Answer 1

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

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

动态编程是一种迭代地解决递归性问题的技术,并且在子问题的计算重叠时适用.

动态编程通常使用制表来实现,但也可以使用memoization来实现.如你所见,两者都不是另一个的"子集".

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

当您使用制表解决动态编程问题时,您可以" 自下而上 " 解决问题,即首先解决所有相关的子问题,通常是填充n维表.基于表中的结果,然后计算"顶部"/原始问题的解决方案.

如果使用memoization来解决问题,可以通过维护已经解决的子问题的映射来实现.你做" 自上而下的,你首先解决"顶"的问题(这通常递归下降解决子问题)的感觉".

这里有一个很好的幻灯片(链接已经死了,幻灯片仍然很好):

• 如果所有子问题必须至少解决一次,那么自下而上的动态编程算法通常比常数因子优于自上而下的memoized算法
  • 递归没有开销,维护表的开销更少
  • 存在一些问题,可以利用动态编程算法中的表访问的规则模式来进一步减少时间或空间要求.
• 如果子问题空间中的某些子问题根本无法解决,那么备忘解决方案的优势就是只解决那些绝对需要的子问题

其他资源:

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

这已被改写为一篇文章在这里.

Answer 2

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

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

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

请参阅关于memoization vs tabulation的讨论.

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

Answer 3

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

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

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

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

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

Answer 4

动态编程通常称为Memoization!

1. Memoization是自上而下的技术(通过分解来开始解决给定的问题)和动态编程是一种自下而上的技术(从普通的子问题开始解决,直到给定的问题)

2. DP通过从基础案例开始查找解决方案并向上运行.DP解决了所有子问题,因为它是自下而上的

   与Memoization不同,它只解决了所需的子问题

3. DP有可能将指数时间强力解决方案转换为多项式时间算法.

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

   相反,Memoization必须支付由递归引起的(通常很大的)开销.

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

Answer 5

(1)从概念上讲,Memoization和DP 实际上是一回事.因为:考虑DP的定义:"重叠子问题"和"最优子结构".Memoization完全拥有这2个.

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

(3)Memoization需要一个哈希表.所以额外的空间,以及一些查找时间.

所以回答这个问题:

- 从概念上讲,(1)意味着它们是相同的.

- 考虑到(2),如果你真的想要,memoization是DP的一个子集,从某种意义上说,DP可以解决由memo化解决的问题,但是DP可以解决的问题可能无法通过memoization解决(因为它可能堆栈溢出).

- 考虑到(3),它们在性能上存在细微差别.

Answer 6

我想举个例子；

问题：

你正在爬楼梯。需要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 7

来自维基百科:

记忆化

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

动态编程

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

当将问题分解为更小/更简单的子问题时,我们经常遇到相同的子问题,因此我们使用Memoization来保存先前计算的结果,因此我们不需要重复它们.

动态编程经常遇到使用memoization有意义的情况,但是你可以使用任何一种技术而不必使用另一种技术.