记忆和动态规划的区别是什么?我认为动态规划是记忆的一个子集。对吗?
当前回答
这是一个记忆和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
}
}
其他回答
我想举个例子;
问题:
你正在爬楼梯。到达顶端需要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/
(1)从概念上讲,记忆和DP其实是一回事。因为:考虑DP的定义:“重叠子问题”和“最优子结构”。记忆完全具备这两点。
(2)在递归较深的情况下,记忆是DP方法,存在栈溢出风险。DP自下而上没有这种风险。
(3)记忆需要一个哈希表。额外的空间和查找时间。
为了回答这个问题:
-从概念上讲,(1)意味着它们是一样的东西。
-考虑(2),如果你真的想,记忆化是DP的一个子集,从某种意义上说,可以通过记忆化解决的问题可以通过DP解决,但是可以通过DP解决的问题可能无法通过记忆化解决(因为它可能会堆栈溢出)。
把(3)考虑在内,它们在性能上有微小的差异。
记忆和动态规划都只解决单个子问题一次。
记忆化使用递归并自顶向下工作,而动态规划则相反,自底向上解决问题。
下面是一个有趣的类比
自上而下-首先你说我将接管世界。你会怎么做呢?你说我会先拿下亚洲。你会怎么做呢?我会先接管印度。我会成为德里的首席部长,等等。
自下而上——你说我会成为德里的首席部长。然后我会接管印度,然后是亚洲所有其他国家,最后我会接管全世界。
在动态规划中,
没有递归的开销,维护表的开销也更少。 表访问的规则模式可用于减少时间或空间需求。
在记忆中,
有些子问题不需要解决。
想想两种方法,
我们把大问题分解成小问题——自顶向下的方法。 我们从最小的子问题开始,到达更大的问题——自下而上的方法。
在Memoization中,我们使用(1.),我们将每个函数调用保存在缓存中,并从那里进行回调。它有点昂贵,因为它涉及到递归调用。
在动态规划中,我们使用(2.)来维护一个表,通过使用保存在表中的数据(通常称为dp-table)自底向上解决子问题。
注意:
两者都适用于具有重叠子问题的问题。 由于递归函数调用期间涉及的开销,内存相对于DP执行得较差。 渐近时间复杂度保持不变。