1

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

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

我的问题是我在这里所说的是否正确？这两种方法看起来很相似，只有 DP 与记忆相比更难，并且在记忆方面的效率略高。有了 memoization，你的程序仍然必须触发每个函数调用，即使它被缓存了，而且这些函数调用中的每一个都可以快速填满堆栈，而在 DP 中它会检查函数内的数组表并且只调用递归/iterative 函数，如果它没有找到。

我在这里正确吗？还是我错过了什么？

4

2 回答 2

1

好吧，我认为您基本上对“记忆化”的定义过于严格，这实际上只是存储先前计算结果而不是重新计算它们的任何技术。因此，将所有结果存储到先前最高n的 Fibonacci 计算正在记忆，但存储先前计算的子问题的 DP 算法也是如此。

（参见维基百科文章。）

于 2012-07-30T04:38:43.153 回答
1

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

来自维基百科：

动态规划方法试图只解决每个子问题一次，从而减少计算次数：一旦计算了给定子问题的解决方案，它就会被存储或“记忆化”：下次需要相同的解决方案时，它简直是抬头。当重复子问题的数量作为输入大小的函数呈指数增长时，这种方法特别有用。

于 2012-07-30T04:45:55.437 回答