记忆记忆

Question

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

但是动态编程稍微好一点，因为它不涉及内存紧张(在递归程序中，参数占用内存，并且随着递归的深入，这种内存会增加)。但在速度方面，两者几乎相等。

但毫无疑问，memoization比动态编程简单得多。

我的问题是:有没有可能在没有内存约束的情况下使用memoization？

Answer 1

您可以将DP看作是一种记忆形式，它受益于对发生什么访问模式的严格保证。Memoization是一个“拉”模型，其中最终的答案请求它的子部分，这些请求(间接地)导致调用的计算的最小粒度。DP是一种“推”模型，在这种模型中，每次计算所需的数据都是可预期的。

可以重新制定任何DP算法，以使用惰性计算和记忆而不是表，有时甚至可以使结果实现在时间和空间复杂度上与DP匹配。然而，第二个技巧通常归结为记住DP实现，并迫使memoization实现“偶然发现”相同的访问模式。这是一个聚会的把戏，不是一个有用的转变。