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

Question

自下而上方法（动态规划）首先查看“较小”的子问题，然后使用较小问题的解决方案来解决较大的子问题。

自上而下在于以“自然的方式”解决问题，并检查您之前是否计算过子问题的解决方案。

我有点困惑。这两者有什么区别？

Answer 1

rev4：用户 Smaron 的一个非常雄辩的评论指出，也许这个答案之前混淆了自上而下和自下而上。虽然最初这个答案（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(2),fib(3),fib(4)... 缓存每个值，以便您可以更轻松地计算下一个值。您也可以将其视为填充表格（另一种形式的缓存）。
  • 我个人很少听到“制表”这个词，但这是一个非常合适的术语。有些人认为这是“动态规划”。
  • 在运行算法之前，程序员会考虑整个树，然后编写一个算法来按特定顺序向根评估子问题，通常会填写一个表格。
  • *脚注：有时“表格”本身并不是具有网格状连接的矩形表格。相反，它可能具有更复杂的结构，例如树，或特定于问题域的结构（例如地图上飞行距离内的城市），甚至是网格图，虽然网格状，但没有上-下-左-右连接结构等。例如，user3290797 链接了一个动态编程示例，该示例查找 一棵树中的最大独立集，对应于树中的填空。

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

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

---

优点和缺点

易于编码

记忆化非常容易编码（您通常可以*编写一个“memoizer”注释或包装函数来自动为您执行此操作），并且应该是你的第一线方法。制表的缺点是您必须提出排序。

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

递归性

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

实际问题

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

最优性

如果您发生（或尝试）访问子问题的顺序不是最优的，特别是如果有不止一种方法来计算子问题（通常缓存可以解决这个问题，但理论上缓存是可能的），那么这两种方法都可能不是时间最优的在某些特殊情况下可能不会）。记忆通常会增加你的时间复杂度和空间复杂度（例如，使用制表你可以更自由地放弃计算，就像使用带有 Fib 的制表可以让你使用 O(1) 空间，但是带有 Fib 的记忆使用 O(N)堆栈空间）。

高级优化

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

---

更复杂的例子

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

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

Answer 2

自上而下和自下而上的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)

我个人认为记忆更加自然。您可以采用递归函数并通过机械过程来记忆它（首先在缓存中查找答案并在可能的情况下返回它，否则递归计算它，然后在返回之前将计算保存在缓存中以供将来使用），而进行自下而上动态编程要求您对计算解决方案的顺序进行编码，这样就不会在它所依赖的较小问题之前计算“大问题”。

Answer 3

动态规划的一个关键特征是存在重叠子问题。也就是说，您试图解决的问题可以分解为子问题，并且许多子问题共享子子问题。这就像“分而治之”，但你最终会多次做同样的事情。我自 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 的一些软件也使用类似的方法）。我会使用自下而上的快速傅里叶变换。

Answer 4

让我们以斐波那契数列为例

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

现在如果我们研究这个算法，它实际上是从较低的值开始，然后转到顶部。如果我需要第五个斐波那契数，我实际上正在计算第一个，然后是第二个，然后是第三个，一直到第五个数。这种技术实际上称为自下而上的技术。

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

Answer 5

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

一般来说，自下而上的方法使用制表技术，而自上而下的方法使用递归（带记忆）技术。

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

自下而上：从基本条件开始，递归地传递到目前为止计算出的值。一般来说，这些都是尾递归。

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

Answer 6

动态规划通常称为记忆化！

1.记忆化是自上而下的技术（通过分解来开始解决给定的问题），动态规划是自下而上的技术（从琐碎的子问题开始解决，向上解决给定的问题）

2.DP找到解决方案从基本案例开始并向上进行。 DP 解决了所有子问题，因为它是自下而上的

与 Memoization 不同，Memoization 仅解决所需的子问题

1. ，DP 具有将指数时间暴力解决方案转换为多项式时间算法的潜力。

2. DP 可能更高效，因为它的迭代

相反，Memoization 必须支付由于递归而产生的（通常是很大的）开销。

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

Answer 7

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

Answer 8

以下是基于 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];
}

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

Answer 9

免责声明：我仍在学习这个主题，我的答案可能不正确......

我觉得这里的答案具有误导性或没有澄清混淆点。

自顶向下

可以轻松地以树形形式可视化

start:

Answer 10

没什么可困惑的...您通常以自下而上的方式学习语言（从基础知识到更复杂的事情），并且经常以自上而下的方式制作您的项目（从总体目标和代码结构到某些部分）实现）

如果涉及逻辑代码示例 - 此处