动态规划(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
 }
}

编程相关文章。指南:动态规划vs记忆vs制表

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

记忆是描述一种优化技术的术语，在这种技术中缓存以前计算的结果，并在再次需要相同的计算时返回缓存的结果。

动态规划是一种迭代求解递归性质问题的技术，适用于子问题的计算重叠的情况。

动态编程通常使用制表实现，但也可以使用记忆实现。所以你可以看到，两者都不是另一个的“子集”。

一个合理的后续问题是:制表(典型的动态编程技术)和记忆之间的区别是什么?

当你用制表法解决一个动态规划问题时，你是“自底向上”地解决问题，也就是说，首先解决所有相关的子问题，通常是填满一个n维表。根据表中的结果，然后计算“顶部”/原始问题的解决方案。

如果您使用记忆来解决问题，您可以通过维护已经解决的子问题的映射来实现。从“自顶向下”的意义上说，首先解决“顶部”问题(通常递归向下解决子问题)。

这里有一个很好的幻灯片(链接现在死了，但幻灯片仍然很好):

If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor No overhead for recursion and less overhead for maintaining table There are some problems for which the regular pattern of table accesses in the dynamic-programming algorithm can be exploited to reduce the time or space requirements even further If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required

额外的资源:

维基百科:记忆，动态规划 相关SO Q/A:动态规划的记忆或制表方法

我想举个例子;

问题:

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

在动态规划中，

没有递归的开销，维护表的开销也更少。 表访问的规则模式可用于减少时间或空间需求。

在记忆中,

有些子问题不需要解决。