知识卡片
独立与重叠是不同维度
同一原问题产生的两个子问题“独立”,指其解不争用资源;
不同递归分支中的子问题“重叠”,指它们其实是同一个状态。
动态规划可同时要求前者便于组合、后者便于缓存,两种性质并不矛盾。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
Two subproblems of the same problem are independent if they do not share resources.
参考来源
- 位置:《算法导论(第4版)》第 14 章问题与章末注释(`OEBPS/chapter014.xhtml`,文本字符 [120000, 122699))。
- 结论依据:第14章脚注6区分两种关系:同一原题的子题独立是资源不共享;在不同递归分支重复出现同一状态则为重叠。
- 原始内容:Two subproblems of the same problem are independent if they do not share resources.