动态规划的一个关键特征是存在重叠的子问题。也就是说，您要解决的问题可以分解为子问题，而这些子问题中的许多都具有子问题。这就像“分而治之”，但你最终会做同样的事情很多很多次。我在2003年教授或解释这些问题时用过一个例子:你可以递归地计算斐波那契数。

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

Use your favorite language and try running it for fib(50). It will take a very, very long time. Roughly as much time as fib(50) itself! However, a lot of unnecessary work is being done. fib(50) will call fib(49) and fib(48), but then both of those will end up calling fib(47), even though the value is the same. In fact, fib(47) will be computed three times: by a direct call from fib(49), by a direct call from fib(48), and also by a direct call from another fib(48), the one that was spawned by the computation of fib(49)... So you see, we have overlapping subproblems.

好消息:不需要多次计算相同的值。计算一次后，缓存结果，下次使用缓存的值!这就是动态规划的本质。你可以称之为“自上而下”，“记忆化”，或者其他你想要的名字。这种方法非常直观，也很容易实现。只需首先编写递归解决方案，在小型测试中测试它，添加内存(缓存已经计算的值)，然后——对了!——你完蛋了。

通常你也可以编写一个等效的迭代程序，从下往上工作，没有递归。在这种情况下，这将是更自然的方法:循环从1到50计算所有的斐波那契数。

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

In any interesting scenario the bottom-up solution is usually more difficult to understand. However, once you do understand it, usually you'd get a much clearer big picture of how the algorithm works. In practice, when solving nontrivial problems, I recommend first writing the top-down approach and testing it on small examples. Then write the bottom-up solution and compare the two to make sure you are getting the same thing. Ideally, compare the two solutions automatically. Write a small routine that would generate lots of tests, ideally -- all small tests up to certain size --- and validate that both solutions give the same result. After that use the bottom-up solution in production, but keep the top-bottom code, commented out. This will make it easier for other developers to understand what it is that you are doing: bottom-up code can be quite incomprehensible, even you wrote it and even if you know exactly what you are doing.

在许多应用程序中，由于递归调用的开销，自底向上方法略快一些。在某些问题中，堆栈溢出也可能是一个问题，请注意，这在很大程度上取决于输入数据。在某些情况下，如果您不够了解动态编程，您可能无法编写导致堆栈溢出的测试，但总有一天这种情况仍会发生。

Now, there are problems where the top-down approach is the only feasible solution because the problem space is so big that it is not possible to solve all subproblems. However, the "caching" still works in reasonable time because your input only needs a fraction of the subproblems to be solved --- but it is too tricky to explicitly define, which subproblems you need to solve, and hence to write a bottom-up solution. On the other hand, there are situations when you know you will need to solve all subproblems. In this case go on and use bottom-up.

我个人会使用自上而下的段落优化，也就是换行优化问题(查找Knuth-Plass换行算法;至少TeX使用它，Adobe Systems的一些软件使用类似的方法)。我会用自底向上的快速傅里叶变换。

下面是DP为基础的解决方案的编辑距离问题，这是自上而下的。我希望它也能帮助你理解动态规划的世界:

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

你可以想象它在你家里的递归实现。如果你以前没有解决过类似的问题，这是非常好的和具有挑战性的。

动态规划问题可以使用自底向上或自顶向下的方法来解决。

通常，自底向上方法使用制表技术，而自顶向下方法使用递归(带记忆)技术。

但是您也可以使用下面所示的递归使用自底向上和自顶向下的方法。

自底向上:从基本条件开始，递归地传递计算到现在的值。一般来说，这些是尾部递归。

int n = 5;
fibBottomUp(1, 1, 2, n);

private int fibBottomUp(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibBottomUp(j, i + j, count + 1, n);
}

自顶向下:从最后一个条件开始，递归地得到它的子问题的结果。

int n = 5;
fibTopDown(n);

private int fibTopDown(int n) {
    if (n <= 1) return 1;
    return fibTopDown(n - 1) + fibTopDown(n - 2);
}

动态规划通常被称为记忆!

1.记忆是一种自顶向下的技术(通过分解来解决给定的问题)，而动态规划是一种自底向上的技术(从微不足道的子问题开始解决，向上到给定的问题)

2.DP通过从基本情况开始并向上工作来找到解决方案。DP解决了所有的子问题，因为它是自下而上的

不像Memoization，它只解决所需的子问题

DP具有将指数时间暴力解转换为多项式时间算法的潜力。 DP可能更有效，因为它是迭代的

相反，Memoization必须支付由于递归而产生的开销(通常很重要)。

更简单地说，Memoization使用自顶向下的方法来解决问题，即从核心(主要)问题开始，然后将其分解为子问题，并以类似的方式解决这些子问题。在这种方法中，同一子问题可能会多次出现，消耗更多的CPU周期，从而增加时间复杂度。而在动态规划中，同一子问题不会求解多次，而是利用其先验结果来优化解。

简单地说，自顶向下方法使用递归一次又一次地调用子问题，而自底向上方法使用单个而不调用任何子问题，因此它更有效。

没什么好困惑的……你通常以自底向上的方式学习语言(从基础到更复杂的东西)，并经常以自顶向下的方式进行项目(从代码的总体目标和结构到某些实现部分)。