1. 华为机考的矩阵乘法计算量估算，考的是“模拟而不是求最优”

华为机考题库里有一道我特别想聊的题，就是“矩阵乘法计算量估算”。它给出一组矩阵的行列数和一串用括号标明顺序的运算式，让你输出完成这个乘法链所需要的标量乘法总次数。我第一次见这道题是在整理机考真题的时候，下意识以为这是纯数学计算，结果上手一写才发现：真正的难点根本不是矩阵乘法本身，而是怎么把括号顺序转化成程序逻辑。

这题适合谁刷呢？我觉得所有准备华为机考的人都可以把它当“保底题”。它不会特别难，题面短，输入规模通常不大，得分点却很明确。准备OD、嵌入式、单板硬件等方向机考的候选人，也会经常在题库里碰到这个题型。主要原因在于这类岗位虽然偏硬件，但机考算法题照样要考数据结构基础，栈和字符串处理就是最常抽中的两板斧。我见过有候选人已经把链表反转背得很熟，结果在这道题上卡了半个多小时，原因不是不会矩阵，而是没想明白括号表达式和栈之间的关系。

更有意思的是，这道题的代码量很少，逻辑看起来也就二十来行，但几乎每一年都有人栽在同一个地方：要么矩阵维度更新错了，要么弹出顺序搞反了，要么表达式读完以后栈里还剩了一堆东西。它表面考的是“计算量估计”，实际上考的是“你能不能把一个数学过程如实翻译成程序”。下面我从题目本身开始，把完整思路、代码、踩坑记录都摊开讲一遍。

1.1 题目入场：输入输出到底长什么样

先来个直观印象。典型题目描述大概是下面这样：

第一行是矩阵个数 n；接下来 n 行每行两个整数，表示第 i 个矩阵的“行数 列数”；最后一行是一个只包含大写字母和括号的表达式，比如 A(B(C(D))) ，表达式中每个字母对应一个矩阵，括号告诉我们先算谁。

举个能直接跑的例子：

3 10 30 30 5 5 60 (A(BC))

这个例子里，A 是 10×30，B 是 30×5，C 是 5×60，计算顺序是先算 B 和 C，再把结果和 A 相乘。最后输出的总乘法次数是 27000，而不是 4500。这里的差别我后面会专门讲。第一次做这道题的人很容易把三个矩阵的维度关系搞混，拿着 10×30、30×5、5×60 三个维度一顿乘，最后也不知道自己算的是哪一步的量。

顺便说一个容易忽略的细节：表达式里的字母顺序并不一定和输入顺序完全对应，但要对应到第几个矩阵，一般是按 A、B、C 从第一个开始映射。也就是说，字母 A 对应第一组行列数，字母 B 对应第二组，依次类推。别看这个映射简单，实际写代码的时候，很多人会在“字母转下标”这一步翻车，尤其是当题目给的矩阵数量超过三个的时候。

1.2 这个题型的三个隐藏考点

第一眼看上去，题目只考矩阵乘法规则，其实它把三样东西揉在了一起。第一是数学基础，你得知道两个矩阵相乘时维度怎么匹配、结果维度怎么变；第二是数据结构，括号嵌套天然适合用栈来处理；第三是工程细节，比如字符串读取、空行、溢出、边界条件。这三样只要有一个没处理好，提交就会 WA。

为什么华为机考喜欢这种题？因为它的区分度很微妙。你给一个完全没准备的人，他也能写出一个看似正确的循环，但一跑样例就错；你给一个准备工作做得好的人，五分钟就能把核心逻辑写完，剩下的时间都在做自测用例。这种题不是靠背模板就能蒙混过关的，它要求你真的理解每一步在算什么。我甚至觉得，它比一些表面复杂的图论题更适合当机考试题，因为代码量少，错误却非常隐蔽。

我见过一个很典型的错误写法：有人只用了一个变量记录总次数，遇到右括号就随手弹栈，却没有把中间结果的维度塞回栈里。这么写在小样例上可能碰巧对，一旦表达式变成三层括号嵌套，立刻全乱。所以刷这道题，重点不是背代码，而是把“栈里到底存的是什么”想明白。

2. 计算量从哪来：矩阵乘法的规则和维度更新

2.1 单个乘法的“性价比”公式

复习一下基础。一个 m×n 的矩阵和一个 n×p 的矩阵相乘，前提是左边矩阵的列数必须等于右边矩阵的行数，结果矩阵是 m×p。运算的时候，结果矩阵里的每一个元素都要做一个长度为 n 的点积，点积里包含 n 次乘法和 n-1 次加法。所以整个乘法过程会执行 m×p×n 次标量乘法。

在机考里，题目说的“计算量估算”通常指的就是标量乘法次数。为什么只看乘法不看加法？因为矩阵乘法里乘法的耗时通常占主导地位，而且机考题目为了简化模型，一般就直接让你统计乘法次数。你可以把它理解成一个“性价比公式”：一次矩阵相乘的代价，等于左矩阵的行数×左矩阵的列数×右矩阵的列数。比如 A 是 10×20，B 是 20×30，那么 A×B 的代价就是 10×20×30=6000，结果矩阵是 10×30。

这里有一个特别容易踩的坑：结果矩阵的维度是左矩阵行数和右矩阵列数。很多人计算完代价以后就忘了更新维度，直接把原来的两个矩阵都丢回栈里。这样到了下一个括号层级，维度信息完全是错的。后面我会在代码部分重点强调这件事。

2.2 括号顺序不同，计算量能差六倍

矩阵乘法满足结合律，但不满足交换律。也就是说 (A×B)×C 和 A×(B×C) 结果矩阵是一样的，但中间的计算量可能差很多。这是这类题最核心的理论背景。

同样用上面的例子：A 是 10×30，B 是 30×5，C 是 5×60。如果先算 A×B，代价是 10×30×5=1500，得到 10×5 的结果矩阵；再和 C 相乘，代价是 10×5×60=3000，总代价 4500。如果先算 B×C，代价是 30×5×60=9000，得到 30×60 的中间矩阵；再和 A 相乘，代价是 10×30×60=18000，总代价 27000。

看见没有，同一个矩阵序列，只是换了个括号位置，计算量差了六倍。所以题目里给的那串括号并不是装饰品，它决定了你每一步先合并哪两个矩阵。这也是为什么这道题不能用“把所有维度乘起来”这种粗暴做法，必须严格模拟表达式指定的计算顺序。

2.3 这里说的“估算”到底在算什么

很多第一次接触这道题的人会疑惑：“估算”是不是意味着只要算个大概就行？完全不是。机考里的“估算”指的是在不模拟具体数字运算的前提下，通过维度推导出理论计算次数，这个结果必须是精准的整数。

这个“估算”和实际机器跑一遍的过程是严格对应的。你每合并两个矩阵，付出的代价就是一次完整矩阵乘法的代价。把所有嵌套步骤的代价累加起来，就是整个乘法链的计算量。你可以把它想象成做账：每一笔矩阵乘法都记一笔账，最后把账单加总。

理解了这一点，你就应该明白为什么栈能起作用了。矩阵乘法的计算顺序本质上是一个带括号的表达式求值过程，而带括号的表达式求值，栈是最顺手的工具。它不是这道题唯一能用的方法，却是代码最简单、最不容易出逻辑错误的方法。

3. 我用栈做完这题的全过程（附 Python/C++ 代码）

3.1 为什么栈能完美贴合括号结构

括号表达式的核心规律是：越靠里的括号越先算，后遇到的右括号对应着最近遇到的左括号，这正好是“后进先出”。所以用栈来模拟计算顺序，思路非常自然：遇到字母就把矩阵维度压栈，遇到右括号就弹出两个矩阵，合并它们，再把这个中间结果压回栈里。

用栈还有一个额外好处：你不用手动维护“当前括号层级”。递归当然也能做，但是递归在处理嵌套层级特别深的长字符串时，可能会出现函数调用栈过深的问题。机考环境一般不会故意卡你递归，但用迭代的栈更稳，时间开销也更低。这道题的复杂度是 O(n + len(expr))，遍历一遍输入就结束，不用动态规划。

3.2 Python 版实现代码

下面是我在实际机考风格环境下常用的 Python 版本。我特意把输入读取写得健壮一点，因为机考平台的测试用例经常会在行尾多出一些空白字符，一不小心就读取错位。

import sys def main(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) idx = 1 dims = [] for _ in range(n): r = int(data[idx]) c = int(data[idx + 1]) idx += 2 dims.append((r, c)) expr = ''.join(data[idx:]) # 最后一行的表达式，可能被拆成多个token stack = [] total = 0 for ch in expr: if ch == '(': continue elif ch == ')': # 弹出顺序：先弹出的是右边矩阵，再弹出的是左边矩阵 right = stack.pop() left = stack.pop() total += left[0] * left[1] * right[1] stack.append((left[0], right[1])) else: i = ord(ch) - ord('A') stack.append(dims[i]) # 兜底：如果表达式没有括号，按从左到右顺序乘完 while len(stack) > 1: right = stack.pop() left = stack.pop() total += left[0] * left[1] * right[1] stack.append((left[0], right[1])) print(total) if __name__ == "__main__": main()

这段代码的核心逻辑只有三件事。第一，括号不处理，只负责把字母压栈和把右括号当作合并触发点。第二，每次遇到右括号，弹两个维度对出来，左边是栈里的倒数第二个，右边是栈顶那个。第三，计算代价以后，把结果矩阵的维度压回去，供外层继续使用。

3.3 C++ 版实现代码

如果你习惯用 C++ 刷题，可以参考下面这版。要注意的地方和 Python 一样，但 C++ 里更明显的问题是数据类型：total 一定要用 long long，不要用 int。稍后我会专门解释为什么。

#include <iostream> #include <string> #include <stack> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<long long, long long>> dims(n); for (int i = 0; i < n; i++) { cin >> dims[i].first >> dims[i].second; } string expr; cin >> expr; stack<pair<long long, long long>> st; long long total = 0; for (char ch : expr) { if (ch == '(') { continue; } else if (ch == ')') { auto right = st.top(); st.pop(); auto left = st.top(); st.pop(); total += left.first * left.second * right.second; st.push(make_pair(left.first, right.second)); } else { int pos = ch - 'A'; st.push(dims[pos]); } } while (st.size() > 1) { auto right = st.top(); st.pop(); auto left = st.top(); st.pop(); total += left.first * left.second * right.second; st.push(make_pair(left.first, right.second)); } cout << total << endl; return 0; }

3.4 手推样例：从入栈到出栈每一行都在干嘛

拿前面那个例子(A(BC))来手动走一遍。初始矩阵：A=10×30，B=30×5，C=5×60。

第一步，遇到左括号，什么都不做。第二步，遇到 A，把 (10,30) 压入栈。第三步，遇到左括号，什么都不做。第四步，遇到 B，把 (30,5) 压入栈。第五步，遇到 C，把 (5,60) 压入栈。此时栈从底到顶是 (10,30), (30,5), (5,60)。

然后遇到第一个右括号。弹出 right=(5,60)，再弹出 left=(30,5)。这两个矩阵是 B 和 C，代价 = 30×5×60 = 9000，中间结果维度是 (30,60)。把 (30,60) 压回栈。此时栈从底到顶是 (10,30), (30,60)。

接着遇到第二个右括号。弹出 right=(30,60)，再弹出 left=(10,30)。这两个是 A 和刚才的中间结果，代价 = 10×30×60 = 18000，中间结果维度 (10,60)。压回栈。此时栈只剩一个 (10,60)，循环结束。

总代价 = 9000 + 18000 = 27000。这和前面表格里的结果完全一致。你可能会问，最后为什么不用管 (10,60)？因为一个结果矩阵本身不会再和别人相乘了，整个过程已经闭环。

3.5 没有括号的“线性顺序”怎么兜底

有些变体题目最后一行可能是一个完全不带括号的字符串，比如ABC。这种情况下，计算顺序被约定为从左到右：先算 A×B，再把结果和 C 乘。如果你的代码只在遇到右括号时才合并，最后栈里会堆着三个维度对，什么都不会输出。

所以我代码里加了一个 while 循环，处理“表达式遍历结束后栈中还剩多个矩阵”的情况。它在栈里从底到顶地反复弹出两个维度对合并，等价于线性从左到右的乘法顺序。如果输入本身就是完整括号表达式，那么遍历结束时栈里必然只剩一个矩阵，这个 while 循环不会进去，不会产生副作用。

这样加一层兜底，代码的通用性会好很多，也不容易因为题目变体而失分。机考平台上很多自称“真题”的题目，细节可能和原版有出入，多做一层保护没有坏处。

4. 我踩过的坑和排查方法

4.1 弹出顺序一错，后面每题都废

这道题最经典的问题，就是左右矩阵搞反。假设栈里底部是 A，顶部是 B，表达式是(AB)，正确的做法是：先弹出 right=B，再弹出 left=A，然后按 left×right 的顺序计算代价。但很多人会顺手写成：先弹出 A，再弹出 B，结果把 A 当成右矩阵，B 当成左矩阵。

这两个顺序对代价的影响有多严重？还是用 A=10×30，B=30×5 来算。正确代价是 10×30×5=1500。如果顺序反了，你会拿 B 的行 30 和 B 的列 5 去乘 A 的列 30，得到 30×5×30=4500。题目可能只让你输出数字，不会提醒你错在矩阵方向，所以这个错误非常隐蔽。

我的经验是，写代码时不要依赖“我记着是弹出 right 再弹出 left”，而是在注释里明确写清楚：栈顶是右操作数，栈顶下面是左操作数。这样每次写回来，都不会再犯迷糊。

4.2 中间结果维度必须塞回栈里

第二高频的错误，是算完两个矩阵相乘以后，忘了把结果矩阵的维度更新回栈里。比如算完 B×C，得到的是 30×60 的矩阵，不是原来的 30×5，也不是 5×60。如果你把其中随便一个原维度压回去，下一层括号继续合并时，算出来的代价就会离谱。

这个问题在表达式嵌套只有一层时不会暴露，因为处理完最内层括号，程序就结束了。但是一旦表达式是A(B(C(D)))这种多层嵌套，每层都要依赖上一层的结果维度，错误会逐层放大。我见过有人第一层结果就错了，后面虽然逻辑没问题，但答案能从几万错到几百万。

我自己后来养成一个习惯：每完成一次弹栈合并，立刻在草稿纸上写一遍此时栈里的内容。写代码前先手推两个不同的样例，能挡住绝大多数维度更新错误。

4.3 读取输入的两种写法，差别很大

机考环境里，输入读取是最容易被忽略的环节。逐行调用input()或readline()没问题，但一旦测试用例在最后一行表达式后面有多余的空行，或者表达式和前面的维度数据之间出现奇怪的空白字符，逐行读取就可能出错。

我更喜欢一次性把整个输入读完，再用 split 切分 token。这样做的好处是，不管中间有多少空白行，程序都能自适应。需要注意的是，表达式这一项可能被 split 切成多个 token，比如( A ( B C ) )这种带空格的写法，所以要用''.join(data[idx:])把它们拼回去。别小看这一行，它能让代码在格式不太规范的测试数据下照样跑对。

4.4 计数类型与溢出问题

矩阵乘法计算量的增长速度比你想象中快。假设一个矩阵链有几十个矩阵，每个维度都是几百，那么一次乘法的代价就是几千万，累计起来很容易突破 int 的范围。C++ 里用 int 保存 total，会在极端数据下溢出成负数；Java 里用 int 同理。Python 的整数是任意精度的，所以没有这个问题，但 C++ 和 Java 一定要用 long long。

我建议在 C++ 代码里把所有维度也一并声明为 long long。这样计算left.first * left.second * right.second时，不会因为中间结果先按 int 运算而溢出，再赋给 long long 时已经来不及了。这个细节在机考环境里就是白送的得分点，别让它丢。

4.5 别和矩阵链动态规划混为一谈

有些人在准备这道题之前，可能先看过更经典的“矩阵链乘法最优括号化”问题，那道题的目标是求最小计算量，解法是区间动态规划。于是一看到“矩阵乘法计算量”几个字，就直接背 DP 模板，结果写了一大堆代码，输出却和题目要求的对不上。

核心区别在于：动态规划题让你在“所有可能的括号方案”里挑最优的；机考这道题直接给你指定了括号顺序，让你去模拟它。有种情况需要额外注意：如果题目真的问了“最小乘法次数”或者“求最优计算顺序”，那才切回动态规划。当前这道题的名字是“计算量估算”，不是“最小计算量”，看到输入里的括号表达式就该秒选栈解法。

5. 考试前怎么把它练成稳定拿分题

5.1 自测样例集：5 分钟验证自己代码

我练这道题的时候，会准备一组覆盖各种边界情况的自测样例。建议你也照这个思路来，不要只跑题目给的那一两个样例。

第一组，单矩阵无乘法，输入 n=1，表达式A，输出 0。这一步能验证程序不会在栈为空时崩溃。第二组，两个矩阵直接相乘，例如A是 10×20，B是 20×30，表达式(AB)，输出 6000。第三组，前面反复提到的三层矩阵，比较(AB)C和A(BC)的输出，确认顺序影响计算量。第四组，多层嵌套表达式，比如A(B(C(D)))，重点检查中间结果维度更新。第五组，无括号表达式ABC，验证 while 兜底逻辑。

这些用例能覆盖绝大多数逻辑盲区。如果跑完这五组都没问题，基本可以放心提交。

5.2 考场时间拆解与代码风格建议

这道题正常难度下，读题加写代码加自测，控制在 15 分钟以内是比较合理的。如果超过 25 分钟还没跑通过，大概率是对栈的模拟过程产生了混淆，建议先在纸上画一遍栈的变化，再继续改代码，而不是盲改。

代码风格方面，我强烈建议变量名不要用 a、b、c 这种含义不明的缩写。机考环境里没人看你的代码，但你自己调试时会看。left、right、rows、cols这种命名能帮你迅速定位问题。另外，在计算代价前加一行注释，写明“代价 = 左矩阵的行数 × 左矩阵的列数 × 右矩阵的列数”，能有效防止自己临时想岔。

5.3 一个可以复用的基础 IO 处理模板

我后来把这类题的输入读取封装成了一个固定模板，刷机考题时直接复用。它的逻辑是：整个输入读进来按空白切割，第一个 token 是 n，往后取 2n 个数字作为矩阵维度，剩余部分用拼接恢复成表达式。这个模板对很多“先给数量，再给一组数据，最后给表达式/查询串”的题型都适用。

def read_input(): data = sys.stdin.read().strip().split() n = int(data[0]) idx = 1 dims = [] for _ in range(n): dims.append((int(data[idx]), int(data[idx + 1]))) idx += 2 expr = ''.join(data[idx:]) return n, dims, expr

把 IO 和算法逻辑分开，调试的时候会更清晰。我个人体会是，这类代码量很小的题，真正吃时间的往往不是算法本身，而是输入边界处理。提前准备好模板，等于把最容易被扣分的地方提前堵住。矩阵乘法计算量估算这道题，值得你在考前静下心来完整亲手写一遍，而不是只看别人的思路。写明白一次之后，以后再遇到带括号的表达式计算类问题，都会觉得顺畅很多。