The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems.
The top-down consists in solving the problem in a "natural manner" and check if you have calculated the solution to the subproblem before.
I'm a little confused. What is the difference between these two?
rev4：用户 Sammaron 的一个非常雄辩的评论指出，也许这个答案以前混淆了自上而下和自下而上。虽然最初这个答案（rev3）和其他答案说“自下而上是记忆”（“假设子问题”），但它可能是相反的（即“自上而下”可能是“假设子问题”和“自下而上”可能是“组成子问题”）。以前，我读过记忆化是一种不同类型的动态编程，而不是动态编程的子类型。尽管我没有订阅它，但我还是引用了这个观点。我已经重写了这个答案，使其与术语无关，直到可以在文献中找到适当的参考资料。我也将此答案转换为社区维基。请选择学术来源。参考文献列表：} {文献：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)... 缓存每个值，以便您可以更轻松地计算下一个值。您也可以将其视为填充表格（另一种形式的缓存）。（在最一般的情况下，在“动态编程”范式中，我会说程序员考虑整个树，然后编写一个算法来实现评估子问题的策略，该策略可以优化您想要的任何属性（通常是时间复杂度和空间复杂度的组合）。您的策略必须从某个特定的子问题开始，并且可能会根据这些评估的结果自行调整。在“动态编程”的一般意义上，您可能会尝试缓存这些子问题，并且更一般地，尝试避免重新访问子问题，其中细微的区别可能是各种数据结构中的图的情况。很多时候，这些数据结构的核心就像数组或表一样。如果我们不再需要子问题的解决方案，可以丢弃它们。）
[以前，这个答案就自上而下与自下而上的术语发表了声明；显然有两种主要的方法称为记忆和制表，它们可能与这些术语存在双射（尽管不完全）。大多数人使用的通用术语仍然是“动态编程”，有些人说“记忆”是指“动态编程”的特定子类型。在社区可以在学术论文中找到适当的参考资料之前，这个答案拒绝说明哪个是自上而下和自下而上的。最终，重要的是理解区别而不是术语。]
记忆很容易编码（您通常可以*编写一个“记忆器”注释或自动为您完成的包装函数），并且应该是您的第一行方法。制表的缺点是您必须提出排序。
*（这实际上只有在您自己编写函数和/或用不纯/非函数式编程语言编码时才容易......例如，如果有人已经编写了预编译fib函数，它必然会对其自身进行递归调用，并且如果不确保那些递归调用调用新的记忆函数（而不是原始的未记忆函数），你就不能神奇地记忆函数）
请注意，自上而下和自下而上都可以通过递归或迭代表格填充来实现，尽管这可能不自然。
使用记忆化，如果树很深（例如fib(10^6)），您将耗尽堆栈空间，因为每个延迟的计算都必须放在堆栈上，并且您将拥有 10^6 个。
如果您发生（或尝试）访问子问题的顺序不是最佳的，特别是如果有不止一种方法来计算子问题（通常缓存可以解决这个问题，但理论上缓存可能在某些异国情调的情况下不是）。记忆通常会将您的时间复杂性添加到您的空间复杂性（例如，使用制表时，您可以更自由地放弃计算，例如使用 Fib 的制表可以让您使用 O(1) 空间，但使用 Fib 的记忆使用 O(N)堆栈空间）。
如果你也在做一个极其复杂的问题，你可能别无选择，只能做制表（或者至少在你想要的记忆中扮演更积极的角色）。此外，如果您处于优化绝对关键并且必须优化的情况下，制表将允许您进行优化，而记忆化不会让您以理智的方式进行。以我的拙见，在正常的软件工程中，这两种情况都不会出现，所以我只会使用 memoization （“缓存其答案的函数”），除非某些东西（例如堆栈空间）使得制表成为必要......虽然从技术上讲，为了避免堆栈井喷，您可以 1）增加允许它的语言中的堆栈大小限制，或 2）消耗恒定的额外工作来虚拟化堆栈（ick），
在这里，我们列出了特别感兴趣的示例，这些示例不仅是一般的 DP 问题，而且有趣地区分了记忆和制表。例如，一个公式可能比另一个容易得多，或者可能存在基本上需要制表的优化：
自顶向下和自底向上 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 年以来，我在教授或解释这些问题时使用了一个示例：您可以递归地计算斐波那契数。
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
使用您最喜欢的语言并尝试将其用于fib(50). 这将需要非常非常长的时间。大约和自己一样多的时间fib(50)！然而，很多不必要的工作正在做。fib(50)将调用fib(49)and fib(48)，但是这两个最终都会调用fib(47)，即使值相同。实际上，fib(47)将计算三次：通过直接调用 from fib(49)，直接调用 from fib(48)，以及直接调用 another fib(48)，由计算产生的fib(49)... 所以你看，我们有重叠的子问题.
好消息：无需多次计算相同的值。计算一次后，缓存结果，下次使用缓存的值！这就是动态规划的本质。您可以将其称为“自上而下”、“记忆”或其他任何您想要的名称。这种方法非常直观，也很容易实现。只需先编写一个递归解决方案，在小测试上对其进行测试，添加记忆（缓存已计算的值），然后 --- 宾果游戏！--- 你完成了。
通常你也可以编写一个等价的迭代程序，自下而上地工作，没有递归。在这种情况下，这将是更自然的方法：从 1 到 50 循环计算所有斐波那契数。
fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]
在任何有趣的场景中，自下而上的解决方案通常更难理解。然而，一旦你理解了它，通常你就会更清楚地了解算法是如何工作的。在实践中，当解决不平凡的问题时，我建议首先编写自顶向下的方法并在小例子上进行测试。然后编写自下而上的解决方案并比较两者以确保您得到相同的东西。理想情况下，自动比较两种解决方案。理想情况下，编写一个可以生成大量测试的小例程——全部小到一定大小的测试 --- 并验证两种解决方案是否给出相同的结果。之后在生产中使用自下而上的解决方案，但保留自上而下的代码，注释掉。这将使其他开发人员更容易理解您在做什么：自下而上的代码可能非常难以理解，即使您编写了它，即使您确切地知道自己在做什么。
在许多应用程序中，由于递归调用的开销，自下而上的方法稍微快一些。在某些问题中，堆栈溢出也可能是一个问题，请注意，这在很大程度上取决于输入数据。在某些情况下，如果您对动态编程不够了解，您可能无法编写导致堆栈溢出的测试，但总有一天这种情况仍然会发生。
现在，存在自顶向下方法是唯一可行的解决方案的问题，因为问题空间太大，不可能解决所有子问题。但是，“缓存”仍然可以在合理的时间内工作，因为您的输入只需要解决一小部分子问题 --- 但明确定义需要解决哪些子问题并因此编写底部 -解决方案。另一方面，在某些情况下，您知道需要解决所有子问题。在这种情况下，继续使用自下而上。
我个人会使用 top-bottom 进行段落优化，也就是Word wrap 优化问题（查找 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
现在让我们以递归斐波那契数列算法为例
public int rcursive(int n) {
if ((n == 1) || (n == 2)) {
return 1;
} else {
return rcursive(n - 1) + rcursive(n - 2);
}
}
现在，如果我们使用以下命令执行此程序
rcursive(5);
如果我们仔细研究算法，为了生成第五个数字，它需要第三个和第四个数字。所以我的递归实际上是从 top(5) 开始，然后一直到底部/较低的数字。这种方法实际上是自上而下的方法。
为了避免多次进行相同的计算，我们使用动态编程技术。我们存储先前计算的值并重用它。这种技术称为记忆化。除了讨论当前问题不需要的记忆之外，动态编程还有更多内容。
自顶向下
让我们重写我们的原始算法并添加记忆技术。
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 个，然后是第 2 个，然后是第 3 个，一直到第 5 个数。这种技术实际上称为自底向上技术。
最后两个，算法完全满足动态规划要求。但一种是自上而下的，另一种是自下而上的。两种算法具有相似的空间和时间复杂度。
动态编程通常称为记忆！
1.记忆是自上而下的技术（通过分解来解决给定的问题），动态规划是自下而上的技术（从琐碎的子问题开始解决，向上到给定的问题）
2.DP通过从基本案例开始找到解决方案并向上工作。DP解决了所有的子问题，因为它是自下而上的
不像记忆，它只解决了需要的子问题
DP 具有将指数时间蛮力解决方案转换为多项式时间算法的潜力。
DP 可能更有效，因为它是迭代的
相反，Memoization 必须支付由于递归而产生的（通常很重要的）开销。
更简单地说，记忆化使用自上而下的方法来解决问题，即它从核心（主要）问题开始，然后将其分解为子问题并类似地解决这些子问题。在这种方法中，相同的子问题可能会发生多次并消耗更多的 CPU 周期，因此会增加时间复杂度。而在动态编程中，相同的子问题不会被多次解决，但先前的结果将用于优化解决方案。
简单地说自上而下的方法使用递归来一次又一次地调用 Sub 问题，而
自下而上的方法使用单个而不调用任何一个，因此它更有效。
动态规划问题可以使用自下而上或自上而下的方法来解决。
通常，自下而上的方法使用制表技术，而自上而下的方法使用递归（带记忆）技术。
但是您也可以使用递归的自下而上和自上而下的方法，如下所示。
自下而上：从基本条件开始，递归地传递到目前为止计算的值。通常，这些是尾递归。
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 的解决方案。我希望它也有助于理解动态编程的世界：
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];
}
您可以在家中考虑它的递归实现。如果您以前没有解决过这样的问题，那将是非常好的和具有挑战性的。