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


当前回答

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

其他回答

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

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

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

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

为了回答这个问题:

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

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

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

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

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

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

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

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

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

Memoization is the top-down technique(start solving the given problem by breaking it down) and dynamic programming is a bottom-up technique(start solving from the trivial sub-problem, up towards the given problem) DP finds the solution by starting from the base case(s) and works its way upwards. DP solves all the sub-problems, because it does it bottom-up Unlike Memoization, which solves only the needed sub-problems DP has the potential to transform exponential-time brute-force solutions into polynomial-time algorithms. DP may be much more efficient because its iterative On the contrary, Memoization must pay for the (often significant) overhead due to recursion.

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

想想两种方法,

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

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

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

注意:

两者都适用于具有重叠子问题的问题。 由于递归函数调用期间涉及的开销,内存相对于DP执行得较差。 渐近时间复杂度保持不变。