记忆记忆

Question

追忆绝对是一种强大的技术。

但是，动态规划稍微好一点，IMO，因为它不涉及内存紧张(在递归程序中，参数占用内存，随着递归的深入，这个内存会增加)。但就速度而言，两者相当平等。

但毫无疑问，回忆录比动态规划要直接得多。

我的问题是:有没有可能在没有记忆约束的情况下使用回忆录？

Answer 1

您可以通过对回忆录值使用“最近使用最少的”缓存 (最大大小有限)来减少用于回忆录的内存量。它的工作效果在很大程度上取决于问题、你将要回忆的函数以及缓存大小的选择。但是，对于DP运行良好的问题，很有可能在计算的第一阶段所需的函数值在某些阶段以后不再需要，因此LRU策略将自动释放这些值的资源。