自下而上的方法（动态编程）包括首先查看“较小的”子问题，然后使用针对较小问题的解决方案解决较大的子问题。
自上而下包括以“自然方式”解决问题，并检查您是否已经计算过子问题的解决方案。
我有点困惑。这两者有什么区别？
rev4：用户Sammaron的一个非常有说服力的评论指出，或许，这个答案以前混淆了自上而下和自下而上。虽然最初这个答案（rev3）和其他答案说“自下而上是记忆”（“假设子问题”），但它可能是反向的（也就是说，“自上而下”可能是“假设子问题”和“自下而上“可能”构成子问题“）。以前，我读过memoization是一种不同的动态编程，而不是动态编程的子类型。尽管没有订阅，但我引用了这个观点。我已经重写了这个答案，对术语不可知，直到在文献中找到适当的参考文献。我还将此答案转换为社区维基。请更喜欢学术资源。参考文献清单：{Web：1，2} {文献：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
（在一些其他罕见的问题中，这棵树在某些分支中可能是无限的，表示非终止，因此树的底部可能无限大。此外，在某些问题中，您可能不知道完整的树在未来之前是什么样的因此，您可能需要一个策略/算法来决定要揭示哪些子问题。）
动态编程至少有两种主要技术并不相互排斥：
fib(100)，你只需要调用它，它会调用fib(100)=fib(99)+fib(98)，它会调用fib(99)=fib(98)+fib(97)，......等......，这将调用fib(2)=fib(1)+fib(0)=1+0=1。然后它最终将解决fib(3)=fib(2)+fib(1)，但它不需要重新计算fib(2)，因为我们缓存它。
这从树的顶部开始，并从叶子/子树到根目录的子问题进行评估。fib(2)，fib(3)，fib(4) ...缓存每个值，以便您可以更轻松地计算下一个值。您还可以将其视为填充表格（另一种形式的缓存）。
我个人并没有经常听到“制表”这个词，但这是一个非常好的术语。有些人认为这是“动态编程”。
在运行算法之前，程序员会考虑整个树，然后编写一个算法，以特定的顺序向根查询子问题，通常填写一个表。
*脚注：有时候，“桌子”本身并不是一个具有网格状连接的矩形桌子。相反，它可能有一个更复杂的结构，例如树，或特定于问题域的结构（例如地图上飞行距离内的城市），甚至是格子图，虽然网格状，但没有例如，user3290797链接了查找maximum independent set in a tree的动态编程示例，该示例对应于填充树中的空白。（最常见的是，在“动态编程”范例中，我会说程序员会考虑整个树，然后编写一个算法来实现一个策略来评估子问题，这个子问题可以优化你想要的任何属性（通常是时间复杂度的组合）你的策略必须从某个特定的子问题开始，或许可以根据这些评估的结果自适应。在“动态编程”的一般意义上，你可能会尝试缓存这些子问题，等等一般来说，尽量避免重新审视子问题，但可能是各种数据结构中图形的细微差别。通常，这些数据结构的核心就像数组或表格一样。如果我们不需要它们，可以抛弃子问题的解决方案了。）
[此前，这个答案对自上而下与自下而上的术语作了陈述;显然有两种称为记忆化和制表的主要方法可能与这些术语一起使用（尽管不完全）。大多数人使用的通用术语仍然是“动态编程”，有些人说“Memoization”是指“动态编程”的特定子类型。这个答案拒绝说明哪个是自上而下和自下而上，直到社区可以在学术论文中找到适当的参考。最终，理解区别而不是术语是很重要的。]
Memoization很容易编码（你通常可以*编写一个“memoizer”注释或自动为你做的包装函数），应该是你的第一线方法。制表的缺点是你必须提出订购。
*（如果您自己编写函数，和/或使用不纯/非函数编程语言编写代码，这实际上很简单...例如，如果某人已经编写了预编译的fib函数，它必然会对自身进行递归调用，并且你不能神奇地记住函数而不确保那些递归调用调用你的新memoized函数（而不是原始的unmemoized函数））
请注意，自上而下和自下而上都可以通过递归或迭代表填充来实现，尽管它可能并不自然。
通过memoization，如果树很深（例如fib(10^6)），你将耗尽堆栈空间，因为每个延迟计算必须放在堆栈上，你将有10 ^ 6个。
如果您发生（或尝试）访问子问题的顺序不是最优的，那么这两种方法可能都不是时间最优的，特别是如果有多种方法来计算子问题（通常缓存会解决这个问题，但理论上可能是缓存可能不是在一些奇特的情况下）。记忆通常会增加你的空间复杂性的时间复杂性（例如，通过制表你可以更自由地扔掉计算，比如使用Fib的制表可以让你使用O（1）空间，但是使用O的记忆使用O（N）堆栈空间）。
如果你也在做一个非常复杂的问题，你可能别无选择，只能做制表（或者至少在你想要它的地方转发备忘录方面发挥更积极的作用）。此外，如果您处于优化至关重要并且必须进行优化的情况下，制表将允许您进行优化，而这些优化将使您无法以理智的方式进行备忘。在我的拙见中，在正常的软件工程中，这两种情况都没有出现过，所以我只会使用memoization（“一种缓存其答案的函数”），除非某些东西（如堆栈空间）需要制表......从技术上讲，为了避免堆栈井喷你可以1）增加允许它的语言的堆栈大小限制，或2）吃一个额外工作的常数因素来虚拟化你的堆栈（ick）或3）程序的延续传递方式，实际上也虚拟化你的堆栈（不确定这个的复杂性，但基本上你将有效地从大小为N的堆栈中取出延迟的调用链，并且事实上将它粘贴在N个连续嵌套的thunk函数中......虽然在某些语言中没有尾部调用优化你可能需要蹦床以避免堆栈井喷）。
在这里，我们列出了特别感兴趣的示例，这些示例不仅仅是一般的DP问题，而且有趣地区分了memoization和制表。例如，一个配方可能比另一个更容易，或者可能存在基本上需要制表的优化：
自上而下和自下而上DP是解决相同问题的两种不同方式。考虑一个记忆（自上而下）与动态（自下而上）编程解决方案来计算斐波那契数。
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)
我个人觉得备忘更加自然。您可以使用递归函数并通过机械过程对其进行记忆（首先在缓存中查找答案并在可能的情况下返回它，否则递归计算它然后在返回之前将计算保存在缓存中以备将来使用），而自下而上动态编程要求您对计算解决方案的顺序进行编码，这样在它所依赖的较小问题之前不会计算出“大问题”。
动态编程的一个关键特性是存在重叠的子问题。也就是说，您尝试解决的问题可以分解为子问题，并且许多子问题共享子问题。这就像“分而治之”，但你最终会做很多次同样的事情。我自2003年以来在教授或解释这些问题时使用的一个例子：你可以递归地计算Fibonacci numbers。
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
使用您最喜欢的语言，并尝试运行fib(50)。这将需要非常长的时间。大约和fib(50)一样多的时间！但是，正在进行许多不必要的工作。 fib(50)将调用fib(49)和fib(48)，但随后这两个人最终将调用fib(47)，即使值相同。实际上，fib(47)将被计算三次：来自fib(49)的直接调用，来自fib(48)的直接调用，以及来自另一个fib(48)的直接调用，由fib(49)的计算产生的那个......所以你看到，我们有重叠的子问题。
好消息：没有必要多次计算相同的值。计算一次后，缓存结果，下次使用缓存值！这是动态编程的本质。您可以将其称为“自上而下”，“备忘录”或其他任何您想要的内容。这种方法非常直观且易于实现。首先编写一个递归解决方案，在小测试中测试它，添加memoization（缓存已计算的值），然后--- bingo！ ---你完成了。
通常你也可以编写一个从下到上工作的等效迭代程序，不需要递归。在这种情况下，这将是更自然的方法：从1到50循环计算所有斐波那契数字。
fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]
在任何有趣的场景中，自下而上的解决方案通常更难以理解。但是，一旦你理解了它，通常你会对算法的运作方式有一个更清晰的大局。在实践中，在解决重要问题时，我建议首先编写自上而下的方法并在小例子上进行测试。然后编写自下而上的解决方案，并比较两者，以确保你得到相同的东西。理想情况下，自动比较两种解决方案。编写一个小例程，可以生成大量测试，理想情况下 - 所有小测试都达到一定的大小 - 并验证两个解决方案都能产生相同的结果。之后在生产中使用自下而上的解决方案，但保留上下代码，注释掉。这将使其他开发人员更容易理解你正在做的事情：自下而上的代码可能是非常难以理解的，即使你写了它，即使你确切知道你在做什么。
在许多应用程序中，由于递归调用的开销，自下而上的方法稍快一些。堆栈溢出在某些问题中也可能是一个问题，请注意，这很大程度上取决于输入数据。在某些情况下，如果您不能很好地理解动态编程，则可能无法编写导致堆栈溢出的测试，但有一天这可能仍会发生。
现在，存在这样的问题：自上而下的方法是唯一可行的解决方案，因为问题空间太大而无法解决所有子问题。然而，“缓存”仍然在合理的时间内工作，因为你的输入只需要解决一小部分子问题 - 但是明确定义你需要解决哪些子问题，从而编写一个底部，这太棘手了。解决方案。另一方面，有些情况下您知道需要解决所有子问题。在这种情况下，继续使用自下而上。
我个人会使用顶部的段落优化a.k.a Word wrap optimization problem（查找Knuth-Plass断行算法;至少TeX使用它，而Adobe Systems的一些软件使用类似的方法）。我会自下而上使用Fast Fourier Transform。
让我们以斐波那契系列为例
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
在前五个斐波纳契数的情况下
Bottom(first) number :1
Top (fifth) number: 5
现在让我们看一下递归Fibonacci系列算法作为例子
public int rcursive(int n) {
if ((n == 1) || (n == 2)) {
return 1;
} else {
return rcursive(n - 1) + rcursive(n - 2);
}
}
现在，如果我们使用以下命令执行此程序
rcursive(5);
如果我们仔细研究算法，为了生成第五个数字，它需要第3个和第4个数字。所以我的递归实际上从顶部（5）开始，然后一直到底部/更低的数字。这种方法实际上是自上而下的方法。
为避免多次进行相同的计算，我们使用动态编程技术。我们存储先前计算的值并重用它。这种技术称为memoization。动态编程除了记忆之外还有更多内容，这是讨论当前问题所不需要的。
自顶向下
让我们重写我们的原始算法并添加memoized技术。
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个数。这种技术实际上称为自下而上的技术。
最后两个，算法全填充动态编程要求。但一个是自上而下的，另一个是自下而上的。两种算法具有相似的空间和时间复杂度。
动态编程通常称为Memoization！
1.Memoization是自上而下的技术（通过分解来开始解决给定的问题）和动态编程是一种自下而上的技术（从普通的子问题开始解决，直到给定的问题）
2.DP通过从基本情况开始找到解决方案并向上工作。 DP解决了所有子问题，因为它是自下而上的
与Memoization不同，它只解决了所需的子问题
相反，Memoization必须支付由递归引起的（通常很大的）开销。
更简单的是，Memoization使用自上而下的方法来解决问题，即它从核心（主要）问题开始，然后将其分解为子问题并类似地解决这些子问题。在这种方法中，相同的子问题可能多次发生并消耗更多的CPU周期，因此增加了时间复杂度。而在动态编程中，相同的子问题将不会被多次解决，但先前的结果将用于优化解决方案。
简单地说自上而下的方法使用递归一次又一次地调用Sub问题 自下而上的方法使用单一而不调用任何一个，因此它更有效。
以下是基于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];
}
您可以在家中想到它的递归实现。如果你之前没有解决过这样的问题，那将是非常好的挑战。