动态规划之备忘录法-白红宇的个人博客

动态规划之备忘录法

发布日期：2021-11-16 18:49:33 浏览次数：5 分类：技术文章

本文共 381 字，大约阅读时间需要 1 分钟。

动态规划与分治方法相似，都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

虽然动态规划算法对每个子子问题只求解一次，但某些子问题在对求解最优解的过程中并无影响，从而不必去求解这类子问题。这里，可以使用备忘录法。

大体思想是：先将每个子问题设为一特定值（如∞）。在求解最优解过程中，当要用到某个子子问题的解时，再去对其进行求解。这种方法可以避免对所有子问题都进行求解，从一定程度上节省了时间开销。

转载地址：https://blog.csdn.net/Thare_Lam/article/details/49643337 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Lab1 Buffer OverFlow

下一篇：Python使用socket传输文件

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章