知识卡片
自底向上遵循依赖顺序
自底向上先解规模更小的切杆状态,填入 r[0…n];计算长度 j 时,所有 r[j−i] 已可直接读取。
通用约束是先算依赖项再算当前项,并非所有动态规划都只需按一个整数长度排序。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
no subproblem is considered until all of the subproblems it depends upon have been solved.
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.1 节(`OEBPS/chapter014.xhtml`,文本字符 [10000, 20000))。
- 结论依据:BOTTOM-UP-CUT-ROD 按长度 j 递增填 r[j],所需 r[j−i] 已算;子问题图一节将通用顺序表述为依赖项先于当前状态。
- 原始内容:no subproblem is considered until all of the subproblems it depends upon have been solved.