时间戳

首页 > 解决方案 > 记忆化被认为是动态编程吗？

java - 记忆化被认为是动态编程吗？

问题描述

我对动态编程和记忆化之间的区别感到困惑。我一直认为它们是完全相同的东西，只是不同的词，但如果不是这样，有人可以澄清它们的意思吗？每次我点击不同的博客时，谷歌都会给我不同的答案。

标签： javac++dynamic

解决方案

Programming.Guide 上的相关文章：动态编程 vs 记忆化 vs 制表

记忆化和动态编程有什么区别？

记忆是一个描述优化技术的术语，您可以在其中缓存先前计算的结果，并在再次需要相同的计算时返回缓存的结果。

动态规划是一种迭代解决递归性质问题的技术，适用于子问题的计算重叠时。

动态编程通常使用制表实现，但也可以使用记忆化来实现。如您所见，两者都不是另一个的“子集”。

一个合理的后续问题是：制表（典型的动态编程技术）和记忆化之间有什么区别？

当您使用制表解决动态规划问题时，您会“自下而上”地解决问题，即首先解决所有相关的子问题，通常是通过填写一个n维表。根据表中的结果，然后计算“顶部”/原始问题的解决方案。

如果您使用记忆化来解决问题，您可以通过维护已经解决的子问题的地图来做到这一点。你是“自上而下”的，因为你首先解决了“顶级”问题（通常会向下递归解决子问题）。

一张从这里开始的好幻灯片（链接现在已经死了，但幻灯片仍然很好）：

  • 如果所有子问题必须至少解决一次，自下而上的动态规划算法通常优于自上而下的记忆算法一个常数因子
    • 没有递归开销，维护表开销更少
    • 对于某些问题，可以利用动态规划算法中的常规表访问模式来进一步减少时间或空间需求
  • 如果子问题空间中的某些子问题根本不需要解决，则记忆解决方案的优点是只解决那些绝对需要的子问题

其他资源：

资料来源：记忆化和动态编程有什么区别？

推荐阅读