dynamic编程和记忆：自下而上和自上而下的方法

我不确定自己是否正确理解了自上而下的方法。

自下而上：是你首先看“小”子问题的地方，然后使用小问题的解决scheme来解决更大的子问题。

自上而下：以自然的方式解决问题，并检查是否已经计算出子问题的解决scheme。

我有点困惑。 有人可以解释吗？ 有什么区别？

Answer 1

rev4：用户Sammaron的一个非常雄辩的评论指出，也许这个答案以前混淆了自上而下和自下而上。 虽然原来这个答案（rev3）和其他答案都说“自下而上”是记忆（也就是“假设子问题”），也可能是倒数（也就是说，“自上而下”可能是“假设子问题”和“自下而上“可能是”构成子问题“）。 之前我已经读过memoization是一种不同types的dynamic规划，而不是dynamic规划的子types，所以引用了尽pipe没有订阅这个观点。 我已经重写了这个答案是不可知的术语，直到在文献中find适当的参考，并将这个答案转换为社区维基。 请select学术来源。 参考文献列表：{Web： 1,2 } {Literature： – }

概括

dynamic编程都是以避免重新计算重复工作的方式对您的计算进行sorting。 你有一个主要问题（你的子树的根）和子问题（子树）。 子问题通常会重复和重叠 。

例如，考虑你最喜欢的Fibonnaci例子。 这是子问题的完整树，如果我们做了一个简单的recursion调用：

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 

（在其他一些罕见的问题中，这棵树在某些分支中可能是无限的，代表不终止，因此树的底部可能是无限大的，而且在一些问题中，你可能不知道完整的树看起来像什么时间，因此你可能需要一个策略/algorithm来决定揭示哪些子问题。）

---

备忘录，制表

至less有两种dynamic编程的主要技术，它们不是相互排斥的：

• 记忆 – 这是一种自由放任的方法：你假设你已经计算了所有的子问题。 你不知道最佳的评估顺序。 你通常从根节点执行recursion调用（或者一些迭代等价的），或者希望你能够接近最优的评估顺序，或者你有一个certificate你会得到最优的评估顺序。 您确保recursion调用从不重新计算子问题，因为您caching结果，因此重复的子树不会重新计算。

  • 例如：如果你正在计算Fibonacci序列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) ，因为我们将其caching起来。
  • 这从树的顶部开始，并且评估叶子/子树中的子问题返回到根。

• 制表 – 您也可以将dynamic编程视为“表格填充”algorithm（虽然通常是多维的，但在非常罕见的情况下，该表格可能具有非欧几里德几何）。 这就像记忆但更加活跃，并且需要一个额外的步骤：您必须提前准确地select您的计算顺序（这并不意味着顺序必须是静态的，而是您有更多的灵活性比记事）。

  • 例如：如果做斐波那契，你select按照这个顺序计算数字： fib(2) ， fib(3) ， fib(4) …caching每个值，以便您可以更容易地计算下一个值。 你也可以把它看作填充表格（另一种forms的caching）。
  • 我个人从来没有听过“制表”这个词，但这是一个很好的词汇。 有些人认为这是“dynamic规划”。
  • 在运行algorithm之前，程序员考虑整个树，然后编写一个algorithm来按照特定的顺序来评估这些子问题，通常填充一个表。
  • *脚注：有时“表”不是一个具有网格状连接本身的矩形表格，而是可能具有更复杂的结构，例如：树或特定于问题域的结构（例如飞行距离内的城市在一个地图上），或者一个网格图（虽然网格状，连接结构不是上下左右）等。例如，user3290797链接了一个dynamic规划的例子， 在树中查找最大独立集 ，这相当于填充树中的空白。

（在最一般的情况下，在“dynamic编程”中，我会说程序员会考虑整个树，然后编写一个algorithm来实现一个评估子问题的策略（它优化你想要的任何属性，通常是时间复杂度和空间 – 复杂度），这个策略必须从某个地方开始，某个特定的子问题，也许根据这些评估的结果进行自我调整，在最一般意义上的“dynamic规划”中，你通常试图caching这些子问题（更一般地说，重新审视子问题……或许在图表的情况下有微妙的区别）在各种数据结构中，这些数据结构常常是像数组或表格一样的核心，如果我们不再需要它们，那么子问题的解决scheme就可以被抛弃。 ）

[以前这个答案是关于自上而下和自下而上术语的陈述; 显然存在两种主要的方法，称为记忆和制表，可能在双向注射这些术语，但不完全。 大多数人使用的通用术语仍然是“dynamic编程”，有些人则说“Memoization”是指dynamic编程的特定子types。 这个答案拒绝说自上而下，自下而上，直到社区可以在学术论文中find适当的参考。 最终理解这个区别而不是术语是很重要的。]

---

优点和缺点

易于编码

记忆是非常容易的代码（你通常可以*写一个“记事本”注释或包装function，自动为你做），应该是你的第一线的方法。 制表的缺点是你必须拿出一个订单。

*（实际上，如果您自己编写函数，并且/或者使用不纯的/非函数式的编程语言进行编码，这实际上是很简单的…例如，如果有人已经编写了预编译的函数，它必然会对自身进行recursion调用，你不能神奇地memome函数没有确保这些recursion调用调用你的新的memoized函数（而不是原始的unmemoized函数））

recursion

请注意，自顶向下和自下而上都可以通过recursion或迭代表填充来实现，尽pipe这可能并不自然。

实际问题

通过记忆，如果树非常深（比如fib(10^6) ），你将会用完堆栈空间，因为每个延迟的计算必须放在堆栈上，而你将有10 ^ 6个堆栈空间。

最优

如果您发生（或尝试）访问子问题的顺序不是最优的，那么两种方法都可能不是最佳的，特别是如果有多种方法来计算子问题（通常高速caching将解决这个问题，但理论上可能的情况是caching可能不是在一些异国情况下）。 记忆通常会增加你复杂的空间复杂性（例如用制表符你可以放弃计算，比如使用带有Fib的制表可以使用O（1）空间，但是用Fib记忆使用O（N）堆栈空间）。

高级优化

如果你也在做一个非常复杂的问题，你可能别无select，只能做制表（或者至less在指导你想要的记忆中扮演更积极的angular色）。 此外，如果您处于优化是绝对关键的情况，而且您必须进行优化，那么制表可以让您执行优化，否则记忆本不会让您以一种理智的方式进行优化。 在我看来，在正常的软件工程中，这两种情况都没有出现，所以我只是使用memoization（“caching它的答案的函数”），除非某些东西（如堆栈空间）使得列表必要。尽pipe从技术上来说，为了避免堆栈爆炸，你可以1）增加允许它的语言的堆栈大小限制，或者2）吃一个额外工作的常量因子来虚拟化你的堆栈（ick），或者3）以连续传递的方式编程，这实际上也是虚拟化你的堆栈（不确定这个的复杂性，但基本上，你将有效地从堆栈大小为N的延迟调用链，事实上坚持在N个连续嵌套的thunk函数…虽然在某些语言没有尾呼优化，你可能不得不蹦床的事情，以避免堆栈井喷）。

---

更复杂的例子

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

• 计算编辑距离的algorithm[ 4 ]，作为二维表格填充algorithm的一个不重要的例子

Answer 2

DP自上而下和自下而上是解决同样问题的两种不同的方式。 考虑计算斐波纳契数字的记忆（自上而下）与dynamic（自下而上）编程解决scheme。

 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) 

我个人发现memoization更自然。 你可以使用一个recursion函数，并通过一个机械过程来记忆它（caching中的第一个查找答案，如果可能的话返回它，否则recursion计算，在返回之前，将答案保存在caching中），而自底向上的dynamic编程需要编码计算解决scheme的顺序，以便在它所依赖的较小问题之前不计算大问题。

Answer 3

dynamic编程的一个关键特征是存在重叠的子问题 。 也就是说，你试图解决的问题可以被分解成多个子问题，其中很多子问题都是子问题。 这就像“分而治之”，但是你最终会做很多次同样的事情。 我从2003年开始教授或解释这些问题时使用过一个例子：您可以recursion地计算斐波纳契数 。

 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(48) ，通过计算fib(49) …所以你看，我们有重叠的子问题 。

好消息：没有必要多次计算相同的值。 一旦你计算一次，caching结果，并在下一次使用caching的值！ 这是dynamic编程的本质。 你可以把它称为“自上而下”，“memoization”，或任何你想要的。 这种方法非常直观，很容易实现。 首先写一个recursion的解决scheme，在小testing上testing，添加记忆（caching已经计算的值），以及—宾果！ —你完成了。

通常你也可以编写一个自下而上的等价迭代程序，无需recursion。 在这种情况下，这将是更自然的方法：从1到50循环计算所有的斐波纳契数字。

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

在任何有趣的情况下，自下而上的解决scheme通常更难以理解。 然而，一旦你明白了，通常你会得到一个更清晰的algorithm如何工作的大图。 在实践中，当我解决平凡的问题的时候，我build议先写自上而下的方法，然后用小的例子进行testing。 然后写下自下而上的解决scheme，并比较两者，以确保你得到同样的东西。 理想情况下，自动比较两个解决scheme。 写一个小程序，会产生大量的testing，理想情况下 – 所有小到一定大小的testing – 并validation两个解决scheme给出相同的结果。 之后，在生产中使用自下而上的解决scheme，但保留自上而下的代码，注释。 这会让其他开发人员更容易理解你在做什么：即使你自己写了，自下而上的代码也是很难理解的，即使你确切地知道你在做什么。

在许多应用程序中，由于recursion调用的开销，自下而上的方法稍微快一点。 堆栈溢出也可能是某些问题的一个问题，请注意，这可能非常依赖于input数据。 在某些情况下，如果您不能很好地理解dynamic编程，则可能无法编写导致堆栈溢出的testing，但总有一天可能会发生。

现在有自顶向下的方法是唯一可行的解​​决scheme，因为问题空间太大，不可能解决所有的子问题。 然而，“caching”仍然在合理的时间内运行，因为你的input只需要解决一小部分子问题—但是明确定义这个问题太棘手，你需要解决哪些子问题，解决scheme。 另一方面，有些情况下，你知道你需要解决所有的子问题。 在这种情况下，继续使用自下而上。

我个人会使用自顶向下的段落优化方法，也就是Word包装优化问题 （查找Knuth-Plass破解algorithm;至lessTeX使用它，而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 

现在让我们来看一个recursion的斐波那契数列algorithm

 public int rcursive(int n) { if ((n == 1) || (n == 2)) { return 1; } else { return rcursive(n - 1) + rcursive(n - 2); } } 

现在，如果我们用下面的命令执行这个程序

 rcursive(5); 

如果仔细观察algorithm，为了生成第五个数字，需要第三个和第四个数字。 所以我的recursion实际上是从顶部（5）开始，然后一直到底部/底部的数字。 这种方法实际上是自上而下的方法。

为了避免多次执行相同的计算，我们使用dynamic编程技术。 我们存储以前计算的值并重新使用它。 这种技术被称为memoization。 还有更多的dynamic编程，然后memoization这是不需要讨论当前的问题。

自上而下

让我们重写我们原来的algorithm，并添加memoized技术。

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

这个解决scheme仍然是自顶向下的，因为algorithm从最高价值开始，每走一步都要到最低价位。

自下而上

但是，问题是，我们能否从底层开始，像从第一个斐波纳契数字开始，然后走上前去。 让我们重写它使用这种技术，

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

现在，如果我们看看这个algorithm，它实际上是从较低的值开始，然后到最高。 如果我需要第五斐波那契数我实际上是计算第一，然后第二，然后第三所有的方式来第五号。 这种技术实际上被称为自下而上的技术。

最后两点，algorithm充满了dynamic规划的要求。 但一个是自上而下，另一个是自下而上。 两种algorithm具有相似的空间和时间复杂度。

Answer 5

dynamic编程通常被称为Memoization！

1.Memoization是自顶向下的技术（通过分解来解决给定的问题），dynamic规划是一种自下而上的技术（从平凡的子问题开始解决，直到给定的问题）

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

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

1. DP有可能将指数时间蛮力解转化为多项式时间algorithm。

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

相反，Memoization必须支付由recursion引起的（经常是重要的）开销。

为了更简单，Memoization使用自上而下的方法来解决问题，即从核心（主要）问题开始，然后将其分解成子问题并类似地解决这些子问题。 在这种方法中，同样的子问题可能会发生多次，消耗更多的CPU周期，从而增加了时间复杂度。 而在dynamic编程中，相同的子问题不会被多次解决，而是使用前面的结果来优化解决scheme。

Answer 6

简单地说，自顶向下的方法使用recursion调用一次又一次的子问题
在哪里自下而上的方式使用单一而不需要调用任何一个，因此效率更高。

Answer 7

以下是自上而下编辑距离问题的基于DP的解决scheme。 我希望这也将有助于理解dynamic规划的世界：

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

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