记忆化和动态编程的区别是什么?我认为动态编程是记忆化的一个子集。是对的吗?
发布于 2021-09-17 15:04:36
这是一个用Java写的来自Fibonacci Number问题的记忆和DP的例子。
这里的动态编程不涉及递归,因为结果更快,并且可以计算更高的值,因为它不受执行堆栈的限制。
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
}
}
https://stackoverflow.com/questions/6184869
复制相似问题