自底向上和自顶向下的区别是什么?

小开

自顶向下和自底向上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:用户Sammaron的一个非常有说服力的评论指出，也许这个答案以前混淆了自上而下和自下而上。虽然最初这个答案(rev3)和其他答案说“自下而上是记忆”(“假设子问题”)，但它可能是相反的(即“自上而下”可能是“假设子问题”，“自下而上”可能是“组成子问题”)。以前，我读过关于记忆是一种不同的动态规划，而不是动态规划的一个子类型的文章。我引用了那个观点，尽管我并不赞同它。我重写了这个答案，直到在文献中找到适当的参考文献。我也把这个答案转换到一个社区wiki上。请选择学术来源。参考文献列表:{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)，因为我们缓存了它。
- 这从树的顶部开始，评估从叶/子树一直到根的子问题。
- 你也可以把动态规划看作是一个“表格填充”算法(虽然通常是多维的，这个“表格”在非常罕见的情况下可能具有非欧几里得几何*)。这类似于记忆，但更活跃，并涉及一个额外的步骤:你必须提前选择你将进行计算的确切顺序。这并不意味着顺序必须是静态的，而是意味着您拥有比记忆更大的灵活性。
  - 例子:如果你正在执行fibonacci，你可以选择按这个顺序计算数字:fib(2)，fib(3)，fib(4)…缓存每个值，以便更容易地计算下一个值。您也可以把它看作是填充一个表(另一种形式的缓存)。
  - 我个人很少听到“制表”这个词，但这是一个非常得体的术语。有人认为这是“动态规划”。
  - 在运行算法之前，程序员考虑整个树，然后编写一个算法，以特定的顺序计算子问题的根，通常填充在一个表中。
  - *脚注:有时“表”本身并不是一个具有网格状连接的矩形表。相反，它可能具有更复杂的结构，例如树状结构，或者特定于问题域的结构(例如，地图上飞行距离内的城市)，甚至是网格图，尽管它类似网格，但没有上下左右的连接结构等。例如，user3290797链接了一个查找树中的最大独立集的动态编程示例，它对应于填充树中的空白。
  (在最一般的情况下，在“动态编程”范例中，我会说程序员考虑整个树，然后编写了一个算法，实现了一种评估子问题的策略，可以优化你想要的任何属性(通常是时间复杂性和空间复杂性的组合)。您的策略必须从某个特定的子问题开始，并且可能会根据这些评估的结果进行自我调整。在一般意义上的“动态规划”中，您可能会尝试缓存这些子问题，更普遍的是，尝试避免重新访问子问题，可能在不同数据结构中的图有细微的区别。通常，这些数据结构的核心是数组或表。如果我们不再需要子问题的解决方案，它们就可以被丢弃。)
  
  [之前，这个答案陈述了自上而下和自下而上的术语;显然有两种主要的方法叫做记忆法和制表法，它们可能与这些术语(尽管不完全)是对立的。大多数人使用的通用术语仍然是“动态规划”，有些人用“记忆”来指代“动态规划”的特定子类型。这个答案拒绝说出哪个是自上而下的，哪个是自下而上的，直到社区在学术论文中找到适当的参考文献。最终，重要的是理解区别而不是术语。
  
  利弊
  
  编码的简易性
  
  记忆化很容易编写代码(你通常可以写一个“memoizer”注释或包装器函数，自动为你完成它)，应该是你的第一行方法。制表的缺点是，你必须提出一个顺序。
  
  *(这实际上只在你自己编写函数，和/或用非纯/非函数式编程语言编码时才容易……例如，如果有人已经编写了一个预编译的fib函数，它必然会对自己进行递归调用，并且如果不确保这些递归调用调用新的已记住的函数(而不是原始的未记住的函数)，你就不能神奇地记住该函数)
  
  递归性
  
  注意，自顶向下和自底向上都可以通过递归或迭代表填充来实现，尽管这可能不是自然的。
  
  实际问题
  
  使用内存，如果树非常深(例如fib(10^6))，你将耗尽堆栈空间，因为每个延迟的计算都必须放在堆栈上，你将有10^6个计算。
  
  最优
  
  如果您发生(或尝试)访问子问题的顺序不是最优的，特别是如果有不止一种方法来计算子问题(通常缓存可以解决这个问题，但理论上在某些特殊情况下缓存可能不能解决)，那么这两种方法都可能不是时间最优的。记忆化通常会增加你的时间复杂度和空间复杂度(例如，使用制表，你有更多的自由来放弃计算，就像使用Fib制表让你使用O(1)空间，但使用Fib记忆化使用O(N)堆栈空间)。
  
  先进的优化
  
  如果您正在处理一个极其复杂的问题，那么您可能别无选择，只能使用制表法(或者至少在引导记忆过程中发挥更积极的作用)。同样，如果你处在一种优化非常关键的情况下，你必须进行优化，制表可以让你进行优化，而记忆法则不能让你以一种正常的方式进行优化。在我看来，在正常的软件工程中，这两种情况都不会出现，所以我只会使用memoization(“缓存其答案的函数”)，除非某些事情(如堆栈空间)使制表成为必要……虽然技术上以避免堆栈防你可以1)增加堆栈大小限制的语言,允许它,或2)吃一个常数因子的额外工作虚拟化您的堆栈(难闻的),或3)计划在连续的传递方式,实际上也虚拟化堆栈(不确定的复杂性,但基本上你有效地将延迟调用链栈的大小N和实际把它先后嵌套铛功能……尽管在一些没有尾部调用优化的语言中，你可能不得不做一些事情来避免堆栈井喷)。
  
  更复杂的例子
  
  在这里，我们列出了一些特别有趣的例子，它们不仅仅是一般的DP问题，而且有趣地区分了记忆法和制表法。例如，一个公式可能比另一个简单得多，或者可能有一个优化基本上需要制表:
  - 计算编辑距离[4]的算法，有趣的是一个二维表格填充算法的非平凡示例

小开

动态规划通常被称为记忆!

1.记忆是一种自顶向下的技术(通过分解来解决给定的问题)，而动态规划是一种自底向上的技术(从微不足道的子问题开始解决，向上到给定的问题)

2.DP通过从基本情况开始并向上工作来找到解决方案。DP解决了所有的子问题，因为它是自下而上的

不像Memoization，它只解决所需的子问题

DP具有将指数时间暴力解转换为多项式时间算法的潜力。

DP可能更有效，因为它是迭代的

相反，Memoization必须支付由于递归而产生的开销(通常很重要)。

更简单地说，Memoization使用自顶向下的方法来解决问题，即从核心(主要)问题开始，然后将其分解为子问题，并以类似的方式解决这些子问题。在这种方法中，同一子问题可能会多次出现，消耗更多的CPU周期，从而增加时间复杂度。而在动态规划中，同一子问题不会求解多次，而是利用其先验结果来优化解。

小开

动态规划的一个关键特征是重叠子问题的存在。也就是说，您要解决的问题可以分解为子问题，而这些子问题中的许多都具有子问题。这就像“分而治之”，但你最终会做同样的事情很多很多次。我在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)的直接调用，以及来自另一个fib(48)的直接调用，该fib(48)是由fib(49)计算生成的…所以你看，我们有fib(50)1。

好消息:不需要多次计算相同的值。计算一次后，缓存结果，下次使用缓存的值!这就是动态规划的本质。你可以称之为“自上而下”，“记忆化”，或者其他你想要的名字。这种方法非常直观，也很容易实现。只需首先编写递归解决方案，在小型测试中测试它，添加内存(缓存已经计算的值)，然后——对了!——你完蛋了。

通常你也可以编写一个等效的迭代程序，从下往上工作，没有递归。在这种情况下，这将是更自然的方法:循环从1到50计算所有的斐波那契数。

fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]

在任何有趣的场景中，自底向上的解决方案通常都更难以理解。然而，一旦你理解了它，通常你会对算法的工作原理有一个更清晰的整体认识。在实践中，当解决非平凡问题时，我建议首先编写自顶向下的方法，并在小示例上测试它。然后编写自底向上的解决方案，并将两者进行比较，以确保得到相同的结果。理想情况下，自动比较两个解决方案。编写一个小例程，生成大量的测试，理想情况下——所有小测试达到一定的大小——并验证两个解决方案给出相同的结果。之后，在生产中使用自底向上的解决方案，但保留自顶向下的代码，将其注释掉。这将使其他开发人员更容易理解您在做什么:自底向上的代码可能非常难以理解，即使是您编写的代码，即使您确切地知道您在做什么。

在许多应用程序中，由于递归调用的开销，自底向上方法略快一些。在某些问题中，堆栈溢出也可能是一个问题，请注意，这在很大程度上取决于输入数据。在某些情况下，如果您不够了解动态编程，您可能无法编写导致堆栈溢出的测试，但总有一天这种情况仍会发生。

现在，有一些问题，自顶向下的方法是唯一可行的解决方案，因为问题空间太大了，不可能解决所有的子问题。然而，“缓存”仍然在合理的时间内工作，因为您的输入只需要解决子问题的一小部分——但是显式定义需要解决哪些子问题并因此编写自底向上的解决方案太棘手了。另一方面，有些情况下，你知道你将需要解决所有子问题。在这种情况下，继续使用自下而上。

我个人会使用自上而下的段落优化，也就是换行优化问题(查找Knuth-Plass换行算法;至少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

对于前5个斐波那契数

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

如果我们仔细研究算法，为了生成第五个数字，它需要第3和第4个数字。所以我的递归实际上是从top(5)开始，然后一直到bottom/lower numbers。这种方法实际上是自顶向下的方法。

为了避免多次进行相同的计算，我们使用动态编程技术。我们存储先前计算的值并重用它。这种技巧叫做记忆。动态规划中除了记忆之外还有更多的内容，在这里不需要讨论。

自顶向下

让我们重写原始算法并添加记忆技术。

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个数字。这种技术实际上叫做自下而上技术。

最后二，算法完全满足动态规划的要求。但一个是自上而下的，另一个是自下而上的。两种算法具有相似的空间复杂度和时间复杂度。

小开

简单地说，自顶向下方法使用递归来反复调用子问题
，而自底向上方法使用单一而不调用任何一个，因此它更有效。

小开

下面是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];
}

你可以想象它在你家里的递归实现。如果你以前没有解决过类似的问题，这是非常好的和具有挑战性的。

小开

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

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

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

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

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

小开

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

自底向上和自顶向下的区别是什么?

回顾

记忆,制表

利弊

编码的简易性

递归性

实际问题

最优

先进的优化

更复杂的例子