记忆和动态规划的区别是什么?我认为动态规划是记忆的一个子集。对吗?
当前回答
动态规划通常被称为记忆!
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执行得较差。 渐近时间复杂度保持不变。
记忆和动态规划都只解决单个子问题一次。
记忆化使用递归并自顶向下工作,而动态规划则相反,自底向上解决问题。
下面是一个有趣的类比
自上而下-首先你说我将接管世界。你会怎么做呢?你说我会先拿下亚洲。你会怎么做呢?我会先接管印度。我会成为德里的首席部长,等等。
自下而上——你说我会成为德里的首席部长。然后我会接管印度,然后是亚洲所有其他国家,最后我会接管全世界。
动态规划是一种求解给定问题的算法范式 将复杂问题分解为子问题并存储结果 以避免再次计算相同的结果。
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周期,从而增加时间复杂度。而在动态规划中,同一子问题不会求解多次,而是利用其先验结果来优化解。
这是一个记忆和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
}
}