动态规划的记忆法或表法

Question

利用动态规划可以解决许多问题，如最长增长子序列。这个问题可以用两种方法来解决。

1. 回溯(自上而下)-使用递归来解决子问题，并将结果存储在哈希表中。
2. 制表(自下而上)-使用迭代方法解决问题，首先解决较小的子问题，然后在执行更大的问题时使用它。

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

Answer 1

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

记忆化通常需要更多的代码，而且不那么简单，但在某些问题上有计算优势，主要是那些不需要计算整个矩阵的所有值才能得到答案的问题。

表格比较简单，但可能会计算不必要的值。但是，如果您确实需要计算所有的值，这个方法通常会更快，因为开销较小。

Answer 2

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

记住，动态规划使用的理想情况是，当您可以重用子问题的解决方案不止一次时，否则，存储结果是没有意义的。

目前，动态规划可以应用于自下而上方法()和自顶向下方法(备忘录)中.

Tabulation：我们首先计算最小子问题的解决方案，然后一次提高一层。基本上遵循自下而上的方法。请注意，我们正在为每个子问题找出详尽的解决方案，而不知道将来是否真的需要它们。

回忆录：我们从原来的问题开始，一直把它分解一个层次，直到我们知道其解决方案的基本情况为止。在大多数情况下，这种分解(自顶向下的方法)是递归的.因此，如果由于递归调用而使用每个步骤的子解决方案，所花费的时间会更慢。但是，如果当不需要所有的子解决方案时，记忆化的效果要好于表。

我发现这个短片很有帮助：https://youtu.be/p4VRynhZYIE

Answer 3

渐近地，一个自顶向下的动态规划实现与自下而上的实现是一样的，假设您使用的是相同的递归关系。然而，自下而上的效率通常更高，因为递归的开销在回忆录中使用。