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的一些软件使用类似的方法)。我会用自底向上的快速傅里叶变换。

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

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

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

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

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

自顶向下和自底向上DP是解决相同问题的两种不同方法。考虑一个记忆(自顶向下)vs动态(自底向上)编程解决方案来计算斐波那契数。

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

我个人觉得记忆更自然。你可以取一个递归函数，并通过一个机械的过程来记忆它(首先在缓存中查找答案，如果可能的话返回它，否则递归地计算它，然后在返回之前，你把计算保存在缓存中以备将来使用)，而做自底向上的动态编程需要你编码一个计算解决方案的顺序，这样就不会在它所依赖的小问题之前计算“大问题”。

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

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]的算法，有趣的是一个二维表格填充算法的非平凡示例