知识卡片

普通读书笔记卡 · 3623.b.2.a.1.a

独立与重叠是不同维度

理解等级:高级

同一原问题产生的两个子问题“独立”,指其解不争用资源;

不同递归分支中的子问题“重叠”,指它们其实是同一个状态。

动态规划可同时要求前者便于组合、后者便于缓存,两种性质并不矛盾。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 14 章问题与章末注释(`OEBPS/chapter014.xhtml`,文本字符 [120000, 122699))。 - 结论依据:第14章脚注6区分两种关系:同一原题的子题独立是资源不共享;在不同递归分支重复出现同一状态则为重叠。 - 原始内容:Two subproblems of the same problem are independent if they do not share resources.