自下而上和自上而下有什么区别？
自下而上方法（动态规划）首先查看“较小”的子问题，然后使用较小问题的解决方案来解决较大的子问题。
自上而下在于以“自然的方式”解决问题，并检查您之前是否计算过子问题的解决方案。
我有点困惑。这两者有什么区别？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
发布评论
评论（10）
自上而下和自下而上的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) 和 fib(48)，但是这两个最终都会调用 fib (47)，即使值相同。事实上，fib(47) 将被计算三次：通过 fib(49) 直接调用、通过 fib(48)< 直接调用/code>，也可以通过另一个 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]
在任何有趣的场景中，自下而上的解决方案通常更难以理解。然而，一旦你真正理解了它，通常你会对算法的工作原理有一个更清晰的了解。在实践中，在解决重要问题时，我建议首先编写自上而下的方法并在小示例上进行测试。然后编写自下而上的解决方案并比较两者以确保您得到相同的结果。理想情况下，自动比较两个解决方案。编写一个小例程，理想情况下会生成大量测试 - 所有 达到一定大小的小测试 - 并验证两种解决方案是否给出相同的结果。之后在生产中使用自下而上的解决方案，但保留自上而下的代码，注释掉。这将使其他开发人员更容易理解您正在做什么：自下而上的代码可能非常难以理解，即使您编写了它，即使您确切地知道自己在做什么。
在许多应用程序中，由于递归调用的开销，自下而上的方法稍微快一些。堆栈溢出也可能是某些问题中的一个问题，请注意，这在很大程度上取决于输入数据。在某些情况下，如果您不太了解动态编程，您可能无法编写导致堆栈溢出的测试，但有一天这种情况仍然可能发生。
现在，存在一些问题，自上而下的方法是唯一可行的解决方案，因为问题空间太大，不可能解决所有子问题。然而，“缓存”仍然在合理的时间内起作用，因为您的输入只需要解决一小部分子问题——但是显式定义您需要解决哪些子问题并因此编写一个底层太棘手了解决方案。另一方面，在某些情况下，您知道需要解决所有子问题。在这种情况下，继续使用自下而上的方法。
我个人会使用从上到下的段落优化，即 自动换行优化问题（查找 Knuth -Plas 断行算法；至少 TeX 使用它，Adobe Systems 的一些软件也使用类似的方法）。我会使用自下而上的快速傅里叶变换。
让我们以斐波那契数列为例
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);
现在，如果我们仔细研究该算法，则 ：为了生成第五个数字，需要第三个和第四个数字。所以我的递归实际上从顶部（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];
}
现在如果我们研究这个算法，它实际上是从较低的值开始，然后转到顶部。如果我需要第五个斐波那契数，我实际上正在计算第一个，然后是第二个，然后是第三个，一直到第五个数。这种技术实际上称为自下而上的技术。
最后两个，算法完全满足动态规划的要求。但一种是自上而下的，另一种是自下而上的。两种算法具有相似的空间和时间复杂度。
动态规划问题可以使用自下而上或自上而下的方法来解决。
一般来说，自下而上的方法使用制表技术，而自上而下的方法使用递归（带记忆）技术。
但您也可以使用递归来采用自下而上和自上而下的方法，如下所示。
自下而上：从基本条件开始，递归地传递到目前为止计算出的值。一般来说，这些都是尾递归。
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 不同，Memoization 仅解决所需的子问题
- ，DP 具有将指数时间暴力解决方案转换为多项式时间算法的潜力。
DP 可能更高效，因为它的迭代
相反，Memoization 必须支付由于递归而产生的（通常是很大的）开销。
更简单地说，Memoization 使用自上而下的方法来解决问题，即从核心（主要）问题开始，然后将其分解为子问题，并以类似的方式解决这些子问题。在这种方法中，相同的子问题可能会出现多次并消耗更多的CPU周期，从而增加时间复杂度。而在动态规划中，相同的子问题不会被多次解决，但先前的结果将用于优化解决方案。
以下是基于 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];
}
你可以在家里想象它的递归实现。如果您以前没有解决过类似的问题，那么这是非常好的且具有挑战性的。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
关于作者
回顾
动态规划就是在一个避免重新计算重复工作的方式。您有一个主要问题（子问题树的根）和子问题（子树）。 子问题通常会重复并重叠。
例如，考虑一下您最喜欢的斐波那契示例。如果我们进行简单的递归调用，这就是完整的子问题树：（
在其他一些罕见问题中，这棵树在某些分支中可能是无限的，代表非终止，因此树的底部可能无限大。此外，在某些问题中，您可能事先不知道完整的树是什么样子，因此，您可能需要一种策略/算法来决定要揭示哪些子问题。）
记忆化、制表
动态规划至少有两种主要技术：不互斥：
记忆 - 这是一种自由放任的方法：您假设您已经计算了所有子问题，并且您不知道最佳评估顺序是什么。通常，您会从根执行递归调用（或某些迭代等效项），并且希望您将接近最佳评估顺序，或者获得将帮助您达到最佳评估顺序的证明。您将确保递归调用永远不会重新计算子问题，因为您缓存结果，因此不会重新计算重复的子树。
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)... 缓存每个值，以便您可以更轻松地计算下一个值。您也可以将其视为填充表格（另一种形式的缓存）。（最一般地说，在“动态编程”范例中，我想说程序员考虑整个树，然后编写一个算法来实现评估子问题的策略，该策略可以优化您想要的任何属性（通常是时间复杂性和空间复杂性的组合）。您的策略必须从某个特定的子问题开始，并且可能会根据这些评估的结果进行自我调整。在“动态规划”的一般意义上，您可以尝试。缓存这些子问题，更一般地说，尽量避免重新审视具有细微区别的子问题，这些子问题可能是各种数据结构中的图形的情况。通常，这些数据结构就像数组或表一样是其核心，子问题的解决方案可以被丢弃。如果我们不再需要它们了。）
[之前，这个答案对自上而下与自下而上的术语进行了陈述；显然有两种主要方法称为“记忆化”和“制表法”，它们可能与这些术语存在双射（尽管不完全）。大多数人使用的通用术语仍然是“动态编程”，有些人说“记忆化”来指代“动态编程”的特定子类型。在社区能够在学术论文中找到适当的参考文献之前，这个答案拒绝说明哪个是自上而下的，哪个是自下而上的。最终，重要的是理解区别而不是术语。]
优点和缺点
易于编码
记忆化非常容易编码（您通常可以*编写一个“memoizer”注释或包装函数来自动为您执行此操作），并且应该是你的第一线方法。制表的缺点是您必须提出排序。
*（实际上，只有当您自己编写函数和/或使用不纯/非函数式编程语言进行编码时，这才容易......例如，如果有人已经编写了预编译的
fib函数，那么它必然会对其自身进行递归调用，并且如果不确保这些递归调用调用新的记忆函数（而不是原始的未记忆函数），您就无法神奇地记忆该函数）递归性
请注意，自上而下和自下而上都可以通过以下方式实现递归或迭代表填充，尽管它可能不自然。
实际问题
对于记忆化，如果树很深（例如
fib(10^6)），您将耗尽堆栈空间，因为每个延迟计算都必须放在堆栈上，并且您将有 10^6 个。最优性
如果您发生（或尝试）访问子问题的顺序不是最优的，特别是如果有不止一种方法来计算子问题（通常缓存可以解决这个问题，但理论上缓存是可能的），那么这两种方法都可能不是时间最优的在某些特殊情况下可能不会）。记忆通常会增加你的时间复杂度和空间复杂度（例如，使用制表你可以更自由地放弃计算，就像使用带有 Fib 的制表可以让你使用 O(1) 空间，但是带有 Fib 的记忆使用 O(N)堆栈空间）。
高级优化
如果您也在做一个极其复杂的问题，您可能别无选择，只能进行制表（或者至少在引导记忆到您想要的地方方面发挥更积极的作用）。此外，如果您处于优化绝对至关重要并且必须优化的情况，制表将允许您进行优化，而记忆则不允许您以理智的方式进行优化。以我的拙见，在正常的软件工程中，这两种情况都不会出现，所以我只会使用记忆化（“缓存其答案的函数”），除非某些东西（例如堆栈空间）使制表成为必要......从技术上讲，为了避免堆栈溢出，您可以1）在允许的语言中增加堆栈大小限制，或2）消耗一定的额外工作来虚拟化堆栈（ick），或3）以连续传递方式进行程序，这实际上还虚拟化了你的堆栈（不确定这的复杂性，但基本上你将有效地从大小为 N 的堆栈中获取延迟调用链，并事实上将其粘贴在 N 个连续嵌套的 thunk 函数中......尽管在某些语言中没有尾部调用优化（您可能必须对事物进行蹦床以避免堆栈溢出）。
更复杂的例子
这里我们列出了特别有趣的例子，它们不仅仅是一般的 DP 问题，而且有趣地区分了记忆化和制表。例如，一种公式可能比另一种公式容易得多，或者可能有一种基本上需要制表的优化：
Recap
Dynamic programming is all about ordering your computations in a way that avoids recalculating duplicate work. You have a main problem (the root of your tree of subproblems), and subproblems (subtrees). The subproblems typically repeat and overlap.
For example, consider your favorite example of Fibonnaci. This is the full tree of subproblems, if we did a naive recursive call:
(In some other rare problems, this tree could be infinite in some branches, representing non-termination, and thus the bottom of the tree may be infinitely large. Furthermore, in some problems you might not know what the full tree looks like ahead of time. Thus, you might need a strategy/algorithm to decide which subproblems to reveal.)
Memoization, Tabulation
There are at least two main techniques of dynamic programming which are not mutually exclusive:
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.
fib(100), you would just call this, and it would callfib(100)=fib(99)+fib(98), which would callfib(99)=fib(98)+fib(97), ...etc..., which would callfib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolvefib(3)=fib(2)+fib(1), but it doesn't need to recalculatefib(2), because we cached it.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.
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).(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.]
Pros and cons
Ease of coding
Memoization is very easy to code (you can generally* write a "memoizer" annotation or wrapper function that automatically does it for you), and should be your first line of approach. The downside of tabulation is that you have to come up with an ordering.
*(this is actually only easy if you are writing the function yourself, and/or coding in an impure/non-functional programming language... for example if someone already wrote a precompiled
fibfunction, it necessarily makes recursive calls to itself, and you can't magically memoize the function without ensuring those recursive calls call your new memoized function (and not the original unmemoized function))Recursiveness
Note that both top-down and bottom-up can be implemented with recursion or iterative table-filling, though it may not be natural.
Practical concerns
With memoization, if the tree is very deep (e.g.
fib(10^6)), you will run out of stack space, because each delayed computation must be put on the stack, and you will have 10^6 of them.Optimality
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).
Advanced optimizations
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).
More complicated examples
Here we list examples of particular interest, that are not just general DP problems, but interestingly distinguish memoization and tabulation. For example, one formulation might be much easier than the other, or there may be an optimization which basically requires tabulation: