知识卡片
备忘录只求所需状态
自顶向下备忘录用特殊值标记未算状态;首次访问递归求值并保存,再次访问直接返回。
若只触及部分状态,可少于自底向上的全表计算;若全部状态必到,自底向上通常少递归与维护开销。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
the memoized solution has the advantage of solving only those subproblems that are definitely required.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.3–14.4 节(`OEBPS/chapter014.xhtml`,文本字符 [60000, 70000))。
- 结论依据:14.3 节指出某些状态可能根本无需访问,备忘录仅求必需状态;若需全表,自底向上可利用明确的访问顺序减少调用开销。
- 原始内容:the memoized solution has the advantage of solving only those subproblems that are definitely required.