自下而上和自上而下有什么区别？

rev4：用户 Sammaron 的一个非常雄辩的评论指出，也许这个答案以前混淆了自上而下和自下而上。虽然最初这个答案（rev3）和其他答案说“自下而上是记忆”（“假设子问题”），但它可能是相反的（即“自上而下”可能是“假设子问题”和“自下而上”可能是“组成子问题”）。以前，我读过记忆化是一种不同类型的动态编程，而不是动态编程的子类型。尽管我没有订阅它，但我还是引用了这个观点。我已经重写了这个答案，使其与术语无关，直到可以在文献中找到适当的参考资料。我也将此答案转换为社区维基。请选择学术来源。参考文献列表：{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(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)...缓存每个值，以便您可以更轻松地计算下一个值。您也可以将其视为填充表格（另一种形式的缓存）。我个人很少听到“制表”这个词，但这是一个非常体面的词。有些人认为这是“动态规划”。在运行算法之前，程序员会考虑整个树，然后编写一个算法来评估子问题以特定顺序朝向根，通常填写一张表。 *脚注：有时“表格”本身并不是具有网格状连接的矩形表格。相反，它可能具有更复杂的结构，例如树，或特定于问题域的结构（例如地图上飞行距离内的城市），甚至是格状图，虽然类似于网格，但没有up-down-left-right 连接结构等。例如，user3290797 链接了一个在树中找到最大独立集的动态规划示例，这对应于填充树中的空白。

示例：如果您正在执行斐波那契，您可以选择按以下顺序计算数字：fib(2),fib(3),fib(4)...缓存每个值，以便您可以更轻松地计算下一个值。您也可以将其视为填充表格（另一种形式的缓存）。

我个人很少听到“制表”这个词，但这是一个非常体面的词。有些人认为这是“动态规划”。

在运行算法之前，程序员会考虑整个树，然后编写一个算法来评估子问题以特定顺序朝向根，通常填写一张表。

*脚注：有时“表格”本身并不是具有网格状连接的矩形表格。相反，它可能具有更复杂的结构，例如树，或特定于问题域的结构（例如地图上飞行距离内的城市），甚至是格状图，虽然类似于网格，但没有up-down-left-right 连接结构等。例如，user3290797 链接了一个在树中找到最大独立集的动态规划示例，这对应于填充树中的空白。

（在最一般的情况下，在“动态编程”范式中，我会说程序员考虑整个树，然后编写一个算法来实现评估子问题的策略，该策略可以优化您想要的任何属性（通常是时间复杂度的组合和空间复杂性）。您的策略必须从某个特定的子问题开始，并且可能会根据这些评估的结果进行调整。在“动态规划”的一般意义上，您可能会尝试缓存这些子问题，等等通常，尽量避免重新审视具有细微差别的子问题，可能是各种数据结构中的图。很多时候，这些数据结构的核心就像数组或表格。如果我们不需要子问题的解决方案，可以丢弃它们不再。）

[以前，这个答案就自上而下与自下而上的术语发表了声明；显然有两种主要的方法称为记忆和制表，它们可能与这些术语存在双射（尽管不完全）。大多数人使用的通用术语仍然是“动态编程”，有些人说“记忆”是指“动态编程”的特定子类型。在社区可以在学术论文中找到适当的参考资料之前，这个答案拒绝说明哪个是自上而下和自下而上的。最终，重要的是理解区别而不是术语。]

优点和缺点

易于编码

记忆很容易编码（您通常可以*编写一个“记忆器”注释或自动为您完成的包装函数），并且应该是您的第一行方法。制表的缺点是您必须提出排序。

*（这实际上只有在您自己编写函数和/或使用不纯/非函数式编程语言进行编码时才容易实现……例如，如果有人已经编写了预编译的 fib 函数，它必然会递归调用本身，如果不确保那些递归调用调用你的新记忆函数（而不是原始的未记忆函数），你就不能神奇地记忆函数）

递归性

请注意，自上而下和自下而上都可以通过递归或迭代表格填充来实现，尽管这可能不自然。

实际问题

使用memoization，如果树很深（例如fib(10^6)），您将耗尽堆栈空间，因为每个延迟的计算都必须放在堆栈上，并且您将有10^6个。

最优性

如果您发生（或尝试）访问子问题的顺序不是最佳的，特别是如果有不止一种方法来计算子问题（通常缓存可以解决这个问题，但理论上缓存可能在某些异国情调的情况下不是）。记忆通常会将您的时间复杂性添加到您的空间复杂性（例如，使用制表您可以更自由地放弃计算，例如使用 Fib 的制表可以让您使用 O(1) 空间，但使用 Fib 的记忆使用 O(N)堆栈空间）。

高级优化

如果你也在做一个非常复杂的问题，你可能别无选择，只能做制表（或者至少在你想要的记忆中扮演更积极的角色）。此外，如果您处于优化绝对关键并且必须优化的情况下，制表将允许您进行优化，而记忆化不会让您以理智的方式进行。以我的拙见，在普通的软件工程中，这两种情况都不会出现，所以我只会使用 memoization（“缓存其答案的函数”），除非某些东西（例如堆栈空间）使得制表成为必要......虽然从技术上讲，为了避免堆栈井喷，您可以 1）增加允许它的语言中的堆栈大小限制，或 2）消耗恒定的额外工作来虚拟化您的堆栈（ick），或 3）以连续传递风格的程序，这实际上还虚拟化了您的堆栈（不确定这的复杂性，但基本上您将有效地从大小为 N 的堆栈中获取延迟调用链并事实上将其粘贴在 N 个连续嵌套的 thunk 函数中......尽管在某些语言中没有尾调用优化，你可能不得不蹦床以避免堆栈井喷）。

更复杂的例子

在这里，我们列出了特别感兴趣的示例，这些示例不仅是一般的 DP 问题，而且有趣地区分了记忆和制表。例如，一个公式可能比另一个容易得多，或者可能存在基本上需要制表的优化：

计算编辑距离的算法[4]，作为二维表格填充算法的重要示例很有趣

---

自顶向下和自底向上 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) 将被计算 3 次：来自 fib(49) 的直接调用、来自 fib(48) 的直接调用以及来自另一个 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 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 

现在让我们以递归斐波那契数列算法为例

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 周期，因此会增加时间复杂度。而在动态编程中，相同的子问题不会被多次解决，但先前的结果将用于优化解决方案。

---

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

通常，自下而上的方法使用制表技术，而自上而下的方法使用递归（带记忆）技术。

但是您也可以使用递归的自下而上和自上而下的方法，如下所示。

自下而上：从基本条件开始，递归地传递到目前为止计算的值。通常，这些是尾递归。

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

---

简单地说自上而下的方法使用递归来一次又一次地调用 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];
}

您可以在家中考虑它的递归实现。如果您以前没有解决过这样的问题，那将是非常好的和具有挑战性的。

---

没什么好混淆的......你通常以自下而上的方式学习语言（从基础到更复杂的东西），并且经常以自上而下的方式制作你的项目（从代码的总体目标和结构到某些部分）实现）

---