知识卡片

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

状态空间须覆盖真实依赖

理解等级:高级

设计动态规划状态时,每种转移产生的子问题都必须还能由同一状态定义表达,这叫依赖闭合。

矩阵链若只定义“前 j 个矩阵 A₁…Aⱼ 的最优成本”,在 k 处分割后,右侧子问题是 Aₖ₊₁…Aⱼ,它不从 A₁ 开始,已经落在前缀状态空间外。把状态改成任意连续区间 (i,j) 后,两个依赖 (i,k) 与 (k+1,j) 才都可表示。

状态数量与每个状态枚举的分割点数量共同决定时间:矩阵链有 Θ(n²) 个区间状态,每个最多试 O(n) 个 k,所以直接填表为 O(n³)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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