动态规划的制表与记忆的性能比较

Question

我正在深入研究动态编程，并试图了解制表和记忆之间的一般性能差异。这两种技术都旨在通过存储中间结果来优化递归算法，以避免冗余计算，但我对它们的整体性能感到好奇。

我的问题是： 考虑到时间复杂度以外的因素，哪种技术在实践中通常表现更好？

制表和记忆在内存使用方面如何比较？是否存在其中一种明显优于另一种的典型场景？

Answer 1

如果你正在考虑

• 制表=自下而上或迭代DP
• 记忆=自上而下或递归DP

自下而上DP的优点：

• 没有递归调用堆栈的开销。因此，它通常具有更好的运行时性能（例外总是适用，见下文）。
• 在某些情况下，您可以实现较低的空间复杂度。例如，在编辑距离问题中，如果您自上而下执行，则递归执行则需要

  O(mn)

  空间，但如果您自下而上执行，则可以一次填充表格一行，从而带来空间复杂度低至

  O(min(m, n))

  （详情请参阅 wikipedia）。

自上而下DP的优点：

• 递归代码非常优雅且易于阅读。如果我不必太担心性能，只是想将时间复杂度从指数级提高到多项式级，那么我通常会出于这个原因而选择自上而下。
• 对于不需要对整个问题空间进行详尽的系统计算的问题，从理论上讲，自上而下的动态规划可能会更高效。举个例子，考虑这个问题：

“给定一个带有

mxn

和

O

的

X

网格，其中

O

为空且

X

被阻塞，找到从左上角单元格到右下角单元格的最短路径，如果你只能向右和向下移动。”

现在想象网格看起来像这样

S O O O O
X X X X O
O O O X O
O O O X O
O O O X E

其中

S

代表开始，

E

代表结束。很明显，从起点到终点只有一条路径。左下角的 3x3

O

岛与这个问题完全无关。

如果你自下而上地解决这个问题，你最终会在找到起始单元格的答案之前找到网格中每个单元格的结果（从底行到顶行）。

如果您通过自上而下的递归进行，它只会考虑唯一可用的路径：

f(0,0) -> f(0, 1) -> f(0, 2) -> f(0, 3) -> f(0, 4) -> f(1, 4) -> f(2, 4) -> f(3, 4) -> f(4, 4)

。

---

如果性能确实很重要，您需要根据现实世界的输入来分析您的算法并做出相应的决定。