我对动态编程和记忆之间的区别感到困惑。我一直认为它们是完全相同的东西,只是不同的词,但如果不是这样,有人能澄清一下它们的意思吗?每次我点击不同的博客,谷歌都会给我不同的答案。
编程相关文章。指南:动态编程vs记忆化vs制表
内存化和动态编程之间的区别是什么
Memoization是一个描述优化技术的术语,在该技术中,您缓存以前计算的结果,并在再次需要相同计算时返回缓存的结果。
动态编程是一种迭代求解递归性质问题的技术,适用于子问题的计算重叠的情况。
动态编程通常使用制表实现,但也可以使用记忆实现。正如你所看到的,两者都不是另一个的"子集"。
一个合理的后续问题是:制表(典型的动态编程技术(和记忆之间有什么区别
当您使用制表法解决动态编程问题时,您可以解决问题">自下而上",即首先解决所有相关的子问题,通常是填写n维表。根据表中的结果,然后计算出"顶部"/原始问题的解决方案。
如果你使用记忆来解决问题,你可以通过维护已经解决的子问题的映射来完成。您可以">自上而下"这样做,即首先解决"顶部"问题(通常向下递归以解决子问题(。
这里的一张好幻灯片(链接现在已经死了,但幻灯片仍然很好(:
- 如果所有子问题都必须至少解决一次,则自下而上的动态编程算法通常比自上而下的记忆算法好一个常数因子
- 没有递归开销,维护表的开销更少
- 对于某些问题,可以利用动态编程算法中的规则表访问模式来进一步减少时间或空间需求
- 如果子问题空间中的一些子问题根本不需要求解,则记忆化解的优点是只求解那些绝对需要的子问题
其他资源:
- 维基百科:记忆化,动态编程
- 相关SO问答:动态编程的记忆化或表格化方法
来源:记忆化和动态编程有什么区别?