知识卡片
矩阵链状态需双端索引
矩阵链的子问题是连续区间 A_i…A_j。
某次分割后会出现右侧中间区间,若只用“从 A1 开始的前缀”作状态,依赖不封闭;必须让起点 i、终点 j 都变化。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第14章 动态规划 · 查看原书依据
For the matrix-chain multiplication problem, a subproblem is to determine the minimum cost of parenthesizing AiAi+1 ⋯ Aj for 1 ≤ i ≤ j ≤ n. Given the input dimensions 〈p0, p1, p2,
参考来源
- 位置:《算法导论(第4版)》第 14 章 14.2–14.3 节(`OEBPS/chapter014.xhtml`,文本字符 [30000, 35000))。
- 结论依据:14.2 节把 Aᵢ…Aⱼ 定为子题并以 (i,j) 标识;分割会产生不从 A₁ 开始的右区间,因此前缀状态对依赖不封闭。
- 原始内容:For the matrix-chain multiplication problem, a subproblem is to determine the minimum cost of parenthesizing A i A i +1 ⋯ A j for 1 ≤ i ≤ j ≤ n . Given the input dimensions 〈 p 0 , p 1 , p 2 , …, p n 〉 , an index pair i , j specifies a subproblem.