time-complexity - 动态规划中记忆递归与表法的时间复杂度比较

Question

动态规划的每个代码在表方法或记忆递归方法中是否具有相同的时间复杂度？

带有适当示例的解决方案将不胜感激。

标签： time-complexitydynamic-programming

Answer 1

时间复杂度- 是（如果您忽略记忆中的函数调用/返回）
空间复杂度- 否。制表可以通过覆盖先前计算但不再需要的值来节省空间。

如本答案的“优化”部分所述 - https://stackoverflow.com/a/6165124/7145074

如果您发生（或尝试）访问子问题的顺序不是最佳的，特别是如果有不止一种方法来计算子问题（通常缓存可以解决这个问题，但理论上缓存可能在某些异国情调的情况下不是）。记忆通常会将您的时间复杂性添加到您的空间复杂性（例如，使用制表时，您可以更自由地放弃计算，例如使用 Fib 的制表可以让您使用 O(1) 空间，但使用 Fib 的记忆使用 O(N)堆栈空间）。

进一步阅读 - https://www.geeksforgeeks.org/tabulation-vs-memoization/