回忆录和动态规划有什么区别?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (25)

我认为动态规划是回忆录的一个子集。是对的吗?

提问于
用户回答回答于

回忆录和动态规划有什么区别?

追忆是一个术语,描述了一种优化技术,您可以缓存以前计算过的结果,并在再次需要相同的计算时返回缓存的结果。

动态规划是一种递归求解问题的技术,在子问题的计算重叠时适用。

动态规划典型使用表格实现,但也可以通过回忆录实现。因此,正如你所看到的,两者都不是另一个的“子集”。

一个合理的后续问题是:图表(典型的动态规划技术)和回忆录有什么区别?

当您使用表格解决动态规划问题时,您就解决了这个问题“自下而上“,即首先解决所有相关的子问题,通常是通过填充n-维度表。然后根据表中的结果,计算出“top”/原问题的解决方案。

如果你用回忆录来解决问题,你可以通过维护已经解决的子问题的地图来解决问题。你去做“自上而下从这个意义上说,你首先解决了“顶”问题。

用户回答回答于

记忆化是一种简单的方法,可以跟踪以前解决的解决方案(通常是作为散列键值对实现的,而不是通常基于数组的表),这样当再次遇到解决方案时就不会重新计算它们。它既可用于自下而上的方法,也可用于自上而下的方法。

因此,动态规划是一种解决某些问题的方法,它通过求解递归关系/递归,并通过列表或回忆录存储先前发现的解。记忆化是一种跟踪以前解决的问题的方法,它可以与对给定输入集具有唯一确定性解的任何函数一起使用。

扫码关注云+社区