知识卡片
记忆化把重复子问题合并
若不同选择路径最终需要相同状态的答案,可以把首次算出的结果缓存,后续直接使用,避免重复展开同一个子问题。楼梯方案数只依当前阶数,朴素两分递归会反复计算相同阶数。
缓存键必须包含决定结果的全部信息,未计算标记也不能与合法结果混淆。记忆化仍使用递归栈,时间改善不等于空间自动常数;计数值很大时还须考虑整数溢出。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
通过存储子问题的解来避免重复计算,从而大幅提升时间效率。 在本节中,我们从一个经典例题入手,先给出它的暴力回溯解法,观察其中包含的重叠子问题,再逐步导出 更高效的动态规划解法。 爬楼梯 给定一个共有 阶的楼梯,你每步可以
参考来源
- 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[6956,7066))
- 结论依据:实际DP定义与楼梯重叠树/dfsMem缓存,强调状态足够与完整存储。
- 原始内容:通过存储子问题的解来避免重复计算,从而大幅提升时间效率。 在本节中,我们从一个经典例题入手,先给出它的暴力回溯解法,观察其中包含的重叠子问题,再逐步导出 更高效的动态规划解法。 爬楼梯 给定一个共有 阶的楼梯,你每步可以