问递归和动态规划的空间复杂度比较，哪个更好？

EN

如果动态编程是以最优方式完成的，则不会。它只是显式地显示了存储需求，这些需求无论如何都会被递归算法隐式地在堆栈上使用。它不会不必要地增加任何额外的空间(除非它是以次优的方式实现的)。

考虑斐波那契计算。递归公式似乎只需要两个值Fib(n+2) = Fib(n+1) + Fib(n)，但由于递归，计算实际上将使用堆栈上的O(n)空间。由于双重递归，时间将是指数的，而随着动态规划从地面开始填充相同的空间，空间和时间都将是线性的。

如果您选择适合动态编程的您最喜欢的问题，例如子集总和，通常有三种方法。

1. Recursion
2. Bottom up dynamic programming.
3. Top down dynamic programming，也就是带记忆的递归。

在时间复杂度方面，递归通常要差一个指数倍，其他两个是等价的。(这就是我们做动态编程的原因。)

就空间需求而言，递归通常是最好的(只需跟踪解决方案的当前尝试)，并且通常(尽管并不总是)自下而上优于自上而下的n (问题的大小)。这是因为您知道何时处理完特定的数据，并可以将其丢弃。

就代码编写的简易性而言，递归通常是最简单的，其次是自上而下，然后是自下而上。(尽管自下而上的内存节省使其值得学习。)

现在您可能会问，在内存和性能之间是否有其他可能的折衷方案？这并不是经常做的，但确实有。一定要自上而下地使用LRU缓存(当缓存变得太大时，您会丢弃其中最近最少使用的值)。您将得到一个不同的权衡，尽管找出折衷是什么有点复杂。