有许多问题可以使用动态规划来解决，例如最长递增子序列。这个问题可以用2种方法解决
- 记忆化（自上而下） - 使用递归解决子问题并将结果存储在某个哈希表中。
- 制表（自下而上） - 使用迭代方法通过首先解决较小的子问题，然后在执行更大的问题时使用它来解决问题。
我的问题是在时间和空间复杂性方面哪种方法更好？
问问题
11610 次
4 回答
41
简短的回答：这取决于问题！
记忆化通常需要更多代码并且不太直接，但在某些问题中具有计算优势，主要是那些您不需要计算整个矩阵的所有值即可得出答案的问题。
制表更直接，但可能会计算不必要的值。但是，如果您确实需要计算所有值，则此方法通常更快，因为开销较小。
于 2012-08-20T18:15:59.020 回答
1
假设您使用相同的递归关系，自上而下的动态编程实现渐近与自下而上相同。然而，由于在记忆中使用递归的开销，自底向上通常更有效。
于 2012-08-20T18:10:04.817 回答
1
首先了解什么是动态规划？ 如果手头的问题可以分解为解决方案也是最优的子问题，并且可以组合以达到原始/更大问题的解决方案。对于此类问题，我们可以应用动态规划。它是通过将子问题的结果存储在程序内存中并重用它而不是在以后重新计算它来解决问题的方法。
请记住，动态编程使用的理想情况是，您可以多次重复使用子问题的解决方案，否则，存储结果就没有意义了。
现在，动态规划可以应用于自下而上的方法（制表）和自上而下的方法（记忆）。
制表：我们从计算最小子问题的解决方案开始，一次升级一个级别。基本上遵循自下而上的方法。请注意，我们正在详尽地为每个子问题寻找解决方案，但不知道将来是否真的需要它们。
记忆：我们从最初的问题开始，不断地把它分解到一个我们知道解决方案的基本案例。在大多数情况下，这种分解（自上而下的方法）是递归的。因此，如果问题是由于递归调用而使用每个步骤的子解决方案，则花费的时间会更慢。但是，如果当时不需要所有子解决方案，则记忆化比制表表现更好。
我发现这个短片很有帮助：https ://youtu.be/p4VRynhZYIE
于 2021-09-25T02:58:10.150 回答
-5
如果问题有overlapping sub-problems属性，则使用Memoization，否则取决于问题
于 2012-08-20T19:57:38.863 回答