动态规划中的记忆化或表格法

Question

有许多问题可以使用动态规划解决，比如最长递增子序列问题。这个问题可以通过以下两种方法之一解决：

1. 备忘录法（自顶向下）- 使用递归来解决子问题，并将结果存储在某个哈希表中。
2. 表格法（自底向上）- 使用迭代方法解决问题，先解决较小的子问题，然后在执行更大的问题时使用它们。

我的问题是哪种方法在时间和空间复杂度方面更好？

- Mady

---

你的第二个选项并不是真正的动态规划，它更像是减治法。它取决于问题的规模和分析中问题试图解决什么。 - squiguy

当然这取决于具体的问题。 - barak1412

如果有一个明确而普遍的答案，生活就会更简单，所有教科书都只会教你“正确”的方法。但是，没有普适的答案。另外，正确的单词是“memoization”，没有字母“R”。 - Novak

为什么要称其为记忆化？似乎用" memorization（记忆）" 更合适，因为我们会记住较小子问题的结果。 - Mady

@Mady http://en.wikipedia.org/wiki/Memoization#Etymology - Ionuț G. Stan

Answer 1

简短回答：这取决于问题！

记忆化通常需要更多的代码，并且不太直观，但对于某些问题具有计算优势，主要是在您不需要计算整个矩阵的所有值以达到答案的情况下。

表格法更加直观易懂，但可能会计算不必要的值。如果您确实需要计算所有值，则由于开销较小，该方法通常更快。

- behnam

Answer 2

首先了解什么是动态规划? 如果一个问题可以被分解成子问题，其解决方案也是最优的，并且可以组合以达到原始/更大问题的解决方案。对于这样的问题，我们可以应用动态规划。 这是一种通过在程序内存中存储子问题的结果并重复使用它而不是在后期重新计算它来解决问题的方法。

记住理想情况下动态编程的使用是，当您可以多次重复使用子问题的解决方案时，否则，存储结果就没有意义。

现在，动态规划可以应用于自底向上（表格法）和自顶向下（备忘录法）。

自底向上（表格法）：我们从计算最小子问题的解决方案开始，并逐级向上进行，基本上遵循自底向上的方法。 注意，在不知道未来是否真正需要这些子问题的情况下，我们正在详尽地找到每个子问题的解决方案。

自顶向下（备忘录法）：我们从原始问题开始，并将其一级一级地分解，直到我们知道其基本情况的解决方案。在大多数情况下，这种分解（自顶向下方法）是递归的。因此，如果问题使用每个步骤的子解决方案，所需的时间会更慢。但是，在所有子解决方案都不需要的情况下，备忘录法比表格法执行得更好。

我发现这个短视频非常有帮助：https://youtu.be/p4VRynhZYIE

- Om Sao

Answer 3

渐进地，如果使用相同的递归关系，自顶向下的动态规划实现与自底向上的实现是相同的。然而，由于记忆化中使用了递归的开销，自底向上的实现通常更有效率。

- weeb

---

我有一个关于这个的问题。 如果我们使用哈希集合和记忆化来存储已经计算过的值，那么在大多数情况下，这不会使记忆化比表格法更有效吗？ - Vatsal Prakash

Answer 4

言之凿凿的答案是：它们在渐进意义上是相同的。

更为细腻的答案是，自顶向下的解决方案通常更符合直觉，并且更能代表动态规划问题中固有的递归关系，它会在深入到基本情况之前懒惰地评估和枚举更大的子问题。只有在你确信每个子问题都将被使用和整合（例如零钱兑换）的情况下，你才会从自底向上而不是自顶向下受益。

在DS&A课程和LeetCode编辑中，因为可怕的“r-word[1]”，人们往往立即排斥自顶向下的解决方案。然而，如果正确实现，自顶向下的动态规划可以与编译器合作，并产生良好执行的优化效果，甚至能够匹敌或超越自下而上、计算制表法。像Combination Sum (I、II、III、IV)系列这样充分利用“惰性求值”的非结构化、即兴问题，以及Advent of Code 2022的第16和第19天的分支限界问题，自顶向下的思维模式都能从中受益。而自下而上的解决方案只会增加家中的取暖器数量。

我通常给人们的一个更互动的例子是用来表示受限分割问题的划分数三角形。通过研究页面上指出的递归关系（p(n, k) = p(n - 1, k = 1) + p(n - k, k)），你可以自下而上地计算整个三角形，或者你可以即时地（自上而下）计算数值，并手动跟踪几组输入，立即就能看出其中一种方法相对较差。

---

^{[1] 递归，你懂的。}

- Jason Nguyen

Answer 5

如果问题具有“重叠子问题”属性，则使用“记忆化”，否则取决于问题本身。

- arunmoezhi

---

对于有重叠子问题的情况，我们也可以使用Tabulation方法。 - Mady

是的，你可以使用，但记忆化会消除冗余计算。 - arunmoezhi

@arunmoezhi 制表符也是如此。 - aioobe