问题背景回顾 #

定义：若矩阵Gi与Gi+1在括号化中直接相乘，则称GiGi+1为显式计算对。

给定矩阵链F₁-F₅的维度：

• F₁: 2×25
• F₂: 25×3
• F₃: 3×16
• F₄: 16×1
• F₅: 1×1000

已知条件：最优括号化的显式计算对为F₃F₄，且F₅需最后参与相乘。

核心直觉思路：最小化中间矩阵的"代价放大效应" #

矩阵乘法的本质代价是「前矩阵行数 × 公共维度 × 后矩阵列数」，而中间矩阵的维度会直接影响后续所有乘法的代价——中间矩阵越大，后续每一步的乘法代价都会被放大。所以我们的核心策略是：优先处理那些能生成最小中间矩阵、同时消除高代价公共维度的相邻矩阵对。

针对本题的具体推导 #

结合题目中F₅最后相乘的约束，我们先聚焦F₁-F₄的处理，目标是让它们最终合并成一个与F₅（1×1000）匹配的矩阵（即列数为1），同时全程最小化中间代价：

1. 逐个分析相邻对的"性价比"：
   • F₁F₂：得到2×3矩阵，代价150，但中间公共维度3还会参与后续乘法；
   • F₂F₃：得到25×16矩阵，代价1200，这个中间矩阵的25行、16列都会大幅拉高后续代价，绝对是优先规避的；
   • F₃F₄：得到3×1矩阵，代价仅48，而且生成的矩阵列数为1——这个维度恰好能完美匹配后续F₅的行数，同时后续和前面的矩阵相乘时，公共维度1几乎不会放大代价；
   • F₄F₅：得到16×1000矩阵，代价高达16000，且违反F₅最后相乘的约束，直接排除。
2. 验证最优路径：
   先处理F₃F₄得到3×1矩阵，再与F₂（25×3）相乘得到25×1矩阵（代价75），接着和F₁（2×25）相乘得到2×1矩阵（代价50），最后和F₅相乘得到2×1000矩阵（代价2000）。总代价远低于其他处理顺序，完全符合最优解要求。

通用直觉步骤总结 #

• 第一步：标记高风险维度——比如本题中的1000、25、16这类数值极大的维度，它们只要作为中间矩阵的行/列，就会大幅提升后续代价，要优先通过相邻相乘消除它们的"重复使用"；
• 第二步：优先锁定低代价相邻对——选择相邻矩阵相乘后，中间矩阵的行和列都尽可能小的对，尤其是能生成极小公共维度（比如本题的1）的对；
• 第三步：结合已知约束调整——如果明确某矩阵最后相乘，就先把它剥离，专注处理剩余链，确保剩余链最终的输出维度能与该矩阵以最小代价相乘。

内容的提问来源于stack exchange，提问作者Geeklovenerds