让我们以斐波那契数列为例

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

换句话说，

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

对于前5个斐波那契数

Bottom(first) number :1
Top (fifth) number: 5 

下面以递归斐波那契数列算法为例

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

现在如果我们用下面的命令执行这个程序

rcursive(5);

如果我们仔细研究算法，为了生成第五个数字，它需要第3和第4个数字。所以我的递归实际上是从top(5)开始，然后一直到bottom/lower numbers。这种方法实际上是自顶向下的方法。

为了避免多次进行相同的计算，我们使用动态编程技术。我们存储先前计算的值并重用它。这种技巧叫做记忆。动态规划中除了记忆之外还有更多的内容，在这里不需要讨论。

自顶向下

让我们重写原始算法并添加记忆技术。

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

我们像下面这样执行这个方法

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

这个解决方案仍然是自顶向下的，因为算法从顶部值开始，每一步都从底部得到我们的顶部值。

自底向上

但问题是，我们能不能从底部开始，比如从第一个斐波那契数开始，然后向上走。我们用这个技巧重写一下，

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

现在，如果我们研究这个算法，它实际上是从较低的值开始，然后向上。如果我需要第5个斐波那契数，我实际上是在计算第1个，然后是第二个，然后是第三个，一直到第5个数字。这种技术实际上叫做自下而上技术。

最后二，算法完全满足动态规划的要求。但一个是自上而下的，另一个是自下而上的。两种算法具有相似的空间复杂度和时间复杂度。

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

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

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

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

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);
}

rev4: A very eloquent comment by user Sammaron has noted that, perhaps, this answer previously confused top-down and bottom-up. While originally this answer (rev3) and other answers said that "bottom-up is memoization" ("assume the subproblems"), it may be the inverse (that is, "top-down" may be "assume the subproblems" and "bottom-up" may be "compose the subproblems"). Previously, I have read on memoization being a different kind of dynamic programming as opposed to a subtype of dynamic programming. I was quoting that viewpoint despite not subscribing to it. I have rewritten this answer to be agnostic of the terminology until proper references can be found in the literature. I have also converted this answer to a community wiki. Please prefer academic sources. List of references: {Web: 1,2} {Literature: 5}

回顾

动态编程就是以一种避免重新计算重复工作的方式对计算进行排序。你有一个主问题(子问题树的根)和一个子问题(子树)。子问题通常重复和重叠。

例如，考虑一下你最喜欢的斐波那奇的例子。这是子问题的完整树，如果我们做一个简单的递归调用:

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

(在其他一些罕见的问题中，该树在某些分支中可能是无穷大的，表示不终止，因此树的底部可能是无穷大的。此外，在某些问题中，您可能事先不知道完整树的样子。因此，你可能需要一个策略/算法来决定揭示哪些子问题。)

---

记忆,制表

至少有两种主要的动态规划技术是互不排斥的:

Memoization - This is a laissez-faire approach: You assume that you have already computed all subproblems and that you have no idea what the optimal evaluation order is. Typically, you would perform a recursive call (or some iterative equivalent) from the root, and either hope you will get close to the optimal evaluation order, or obtain a proof that you will help you arrive at the optimal evaluation order. You would ensure that the recursive call never recomputes a subproblem because you cache the results, and thus duplicate sub-trees are not recomputed. example: If you are calculating the Fibonacci sequence fib(100), you would just call this, and it would call fib(100)=fib(99)+fib(98), which would call fib(99)=fib(98)+fib(97), ...etc..., which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn't need to recalculate fib(2), because we cached it. This starts at the top of the tree and evaluates the subproblems from the leaves/subtrees back up towards the root. Tabulation - You can also think of dynamic programming as a "table-filling" algorithm (though usually multidimensional, this 'table' may have non-Euclidean geometry in very rare cases*). This is like memoization but more active, and involves one additional step: You must pick, ahead of time, the exact order in which you will do your computations. This should not imply that the order must be static, but that you have much more flexibility than memoization. example: If you are performing fibonacci, you might choose to calculate the numbers in this order: fib(2),fib(3),fib(4)... caching every value so you can compute the next ones more easily. You can also think of it as filling up a table (another form of caching). I personally do not hear the word 'tabulation' a lot, but it's a very decent term. Some people consider this "dynamic programming". Before running the algorithm, the programmer considers the whole tree, then writes an algorithm to evaluate the subproblems in a particular order towards the root, generally filling in a table. *footnote: Sometimes the 'table' is not a rectangular table with grid-like connectivity, per se. Rather, it may have a more complicated structure, such as a tree, or a structure specific to the problem domain (e.g. cities within flying distance on a map), or even a trellis diagram, which, while grid-like, does not have a up-down-left-right connectivity structure, etc. For example, user3290797 linked a dynamic programming example of finding the maximum independent set in a tree, which corresponds to filling in the blanks in a tree.

(At it's most general, in a "dynamic programming" paradigm, I would say the programmer considers the whole tree, then writes an algorithm that implements a strategy for evaluating subproblems which can optimize whatever properties you want (usually a combination of time-complexity and space-complexity). Your strategy must start somewhere, with some particular subproblem, and perhaps may adapt itself based on the results of those evaluations. In the general sense of "dynamic programming", you might try to cache these subproblems, and more generally, try avoid revisiting subproblems with a subtle distinction perhaps being the case of graphs in various data structures. Very often, these data structures are at their core like arrays or tables. Solutions to subproblems can be thrown away if we don't need them anymore.)

[Previously, this answer made a statement about the top-down vs bottom-up terminology; there are clearly two main approaches called Memoization and Tabulation that may be in bijection with those terms (though not entirely). The general term most people use is still "Dynamic Programming" and some people say "Memoization" to refer to that particular subtype of "Dynamic Programming." This answer declines to say which is top-down and bottom-up until the community can find proper references in academic papers. Ultimately, it is important to understand the distinction rather than the terminology.]

---

利弊

编码的简易性

记忆化很容易编写代码(你通常可以写一个“memoizer”注释或包装器函数，自动为你完成它)，应该是你的第一行方法。制表的缺点是，你必须提出一个顺序。

*(这实际上只在你自己编写函数，和/或用非纯/非函数式编程语言编码时才容易……例如，如果有人已经编写了一个预编译的fib函数，它必然会对自己进行递归调用，如果不确保这些递归调用调用新的已记函数(而不是原来的未记函数)，你就不能神奇地记住这个函数。

递归性

注意，自顶向下和自底向上都可以通过递归或迭代表填充来实现，尽管这可能不是自然的。

实际问题

使用内存，如果树非常深(例如fib(10^6))，你将耗尽堆栈空间，因为每个延迟的计算都必须放在堆栈上，你将有10^6个。

最优

Either approach may not be time-optimal if the order you happen (or try to) visit subproblems is not optimal, specifically if there is more than one way to calculate a subproblem (normally caching would resolve this, but it's theoretically possible that caching might not in some exotic cases). Memoization will usually add on your time-complexity to your space-complexity (e.g. with tabulation you have more liberty to throw away calculations, like using tabulation with Fib lets you use O(1) space, but memoization with Fib uses O(N) stack space).

先进的优化

If you are also doing a extremely complicated problems, you might have no choice but to do tabulation (or at least take a more active role in steering the memoization where you want it to go). Also if you are in a situation where optimization is absolutely critical and you must optimize, tabulation will allow you to do optimizations which memoization would not otherwise let you do in a sane way. In my humble opinion, in normal software engineering, neither of these two cases ever come up, so I would just use memoization ("a function which caches its answers") unless something (such as stack space) makes tabulation necessary... though technically to avoid a stack blowout you can 1) increase the stack size limit in languages which allow it, or 2) eat a constant factor of extra work to virtualize your stack (ick), or 3) program in continuation-passing style, which in effect also virtualizes your stack (not sure the complexity of this, but basically you will effectively take the deferred call chain from the stack of size N and de-facto stick it in N successively nested thunk functions... though in some languages without tail-call optimization you may have to trampoline things to avoid a stack blowout).

---

更复杂的例子

在这里，我们列出了一些特别有趣的例子，它们不仅仅是一般的DP问题，而且有趣地区分了记忆法和制表法。例如，一个公式可能比另一个简单得多，或者可能有一个优化基本上需要制表:

计算编辑距离[4]的算法，有趣的是一个二维表格填充算法的非平凡示例

动态规划的一个关键特征是存在重叠的子问题。也就是说，您要解决的问题可以分解为子问题，而这些子问题中的许多都具有子问题。这就像“分而治之”，但你最终会做同样的事情很多很多次。我在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的一些软件使用类似的方法)。我会用自底向上的快速傅里叶变换。

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

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