知识卡片

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

矩阵链状态需双端索引

理解等级:高级

矩阵链的子问题是连续区间 A_i…A_j。

某次分割后会出现右侧中间区间,若只用“从 A1 开始的前缀”作状态,依赖不封闭;必须让起点 i、终点 j 都变化。

这张卡片看不懂?

已有反馈 · 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.