知识卡片

普通读书笔记卡 · 3623.c

自底向上遵循依赖顺序

理解等级:中级

自底向上先解规模更小的切杆状态,填入 r[0…n];计算长度 j 时,所有 r[j−i] 已可直接读取。

通用约束是先算依赖项再算当前项,并非所有动态规划都只需按一个整数长度排序。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.