memoization与动态编程查找的实现

Question

在我开始之前，不，这不是一个问题，问记忆化和动态编程之间的区别，也不是哪个更好，而是一个简单的问题，问他们处理缓存查找的方式之间的细微差别。

DP使用自下而上的方法，而memoization使用自上而下的方法。因此，对于DP，您首先构建一个缓存计算表，然后将这些缓存值提供给更大的计算，以避免多余的递归或迭代函数调用。Memoization或多或少只是将每个函数调用的结果缓存到一个散列或数组(可能是一个数组)中，然后在函数调用中提供结果(它只是跳过函数体中发生的任何事情)。

我的问题是，我在这里所说的是正确的吗？这两种方法看起来很相似，只是DP比memoization更难，并且在内存方面略有效率。使用memoization，你的程序仍然必须触发每个函数调用，即使它被缓存了，并且每个函数调用都可以快速地填充堆栈，而在DP中，它将检查函数中的数组表，只有在找不到递归/迭代函数时才调用它。

我说的对吗？还是我错过了什么？

Answer 1

嗯，我认为你对“记忆化”的定义过于严格了，“记忆化”实际上是存储先前计算结果的任何技术，而不是重新计算它们。因此，存储直到前一个高n的所有结果的Fibonacci计算是记忆，但存储先前计算的子问题的DP算法也是记忆。

(请参阅Wikipedia article。)

Answer 2

动态编程和记忆化并不是互斥的，也不是不同的方法。Memo-ization只是“记住”函数调用的结果，以及它的所有相关上下文(参数、调用实例等)。动态规划使用记忆法来实现只计算一次给定子问题的结果的目标。

来自Wikipedia

动态编程方法寻求只解决每个子问题一次，从而减少计算次数:一旦计算出给定子问题的解决方案，它就会被存储或“记忆”：下次需要相同的解决方案时，只需查找即可。当重复的子问题的数量随着输入的大小呈指数级增长时，这种方法特别有用。