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

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

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

为了回答这个问题:

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

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

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

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

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

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

为了回答这个问题:

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

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

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

我想举个例子;

问题:

你正在爬楼梯。到达顶端需要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/

动态规划(DP)和记忆化之间有一些相似之处，在大多数情况下，您可以通过记忆实现动态规划过程，反之亦然。但它们确实有一些区别，你应该在决定使用哪种方法时查看它们:

Memoization is a top-down approach during which you decompose a big problem into smaller-size subproblems with the same properties and when the size is small enough you can easily solve it by bruteforcing. Dynamic Programming is a bottom-up approach during which you firstly calculate the answer of small cases and then use them to construct the answer of big cases. During coding, usually memoization is implemented by recursion while dynamic programming does calculation by iteration. So if you have carefully calculate the space and time complexity of your algorithm, using dynamic-programming-style implementation can offer you better performance. There do exist situations where using memoization has advantages. Dynamic programming needs to calculate every subproblem because it doesn't know which one will be useful in the future. But memoization only calculate the subproblems related to the original problem. Sometimes you may design a DP algorithm with theoretically tremendous amount of dp status. But by careful analyses you find that only an acceptable amount of them will be used. In this situation it's preferred to use memoization to avoid huge execution time.

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

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