知识卡片
状态空间须覆盖真实依赖
设计动态规划状态时,每种转移产生的子问题都必须还能由同一状态定义表达,这叫依赖闭合。
矩阵链若只定义“前 j 个矩阵 A₁…Aⱼ 的最优成本”,在 k 处分割后,右侧子问题是 Aₖ₊₁…Aⱼ,它不从 A₁ 开始,已经落在前缀状态空间外。把状态改成任意连续区间 (i,j) 后,两个依赖 (i,k) 与 (k+1,j) 才都可表示。
状态数量与每个状态枚举的分割点数量共同决定时间:矩阵链有 Θ(n²) 个区间状态,每个最多试 O(n) 个 k,所以直接填表为 O(n³)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
both i and j need to vary in the subproblem of parenthesizing the product
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.2–14.3 节(`OEBPS/chapter014.xhtml`,文本字符 [45000, 50000))。
- 结论依据:14.3 节指出矩阵链分割的右子题 Aₖ₊₁…Aⱼ 不是从 A₁ 起的前缀,故状态两端 i、j 都须变化;状态与候选数量还决定计算量。
- 原始内容:both i and j need to vary in the subproblem of parenthesizing the product