什么是记忆化和动态规划的区别？

这是一个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
 }
}

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