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

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

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

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

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周期，从而增加时间复杂度。而在动态规划中，同一子问题不会求解多次，而是利用其先验结果来优化解。

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

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

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

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

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