1. 華為機考的矩陣乘法計算量估算考的是“模擬而不是求最優(yōu)”華為機考題庫里有一道我特別想聊的題就是“矩陣乘法計算量估算”。它給出一組矩陣的行列數(shù)和一串用括號標明順序的運算式讓你輸出完成這個乘法鏈所需要的標量乘法總次數(shù)。我第一次見這道題是在整理機考真題的時候下意識以為這是純數(shù)學計算結果上手一寫才發(fā)現(xiàn)真正的難點根本不是矩陣乘法本身而是怎么把括號順序轉化成程序邏輯。這題適合誰刷呢我覺得所有準備華為機考的人都可以把它當“保底題”。它不會特別難題面短輸入規(guī)模通常不大得分點卻很明確。準備OD、嵌入式、單板硬件等方向機考的候選人也會經常在題庫里碰到這個題型。主要原因在于這類崗位雖然偏硬件但機考算法題照樣要考數(shù)據結構基礎棧和字符串處理就是最常抽中的兩板斧。我見過有候選人已經把鏈表反轉背得很熟結果在這道題上卡了半個多小時原因不是不會矩陣而是沒想明白括號表達式和棧之間的關系。更有意思的是這道題的代碼量很少邏輯看起來也就二十來行但幾乎每一年都有人栽在同一個地方要么矩陣維度更新錯了要么彈出順序搞反了要么表達式讀完以后棧里還剩了一堆東西。它表面考的是“計算量估計”實際上考的是“你能不能把一個數(shù)學過程如實翻譯成程序”。下面我從題目本身開始把完整思路、代碼、踩坑記錄都攤開講一遍。1.1 題目入場輸入輸出到底長什么樣先來個直觀印象。典型題目描述大概是下面這樣第一行是矩陣個數(shù) n接下來 n 行每行兩個整數(shù)表示第 i 個矩陣的“行數(shù) 列數(shù)”最后一行是一個只包含大寫字母和括號的表達式比如 A(B(C(D))) 表達式中每個字母對應一個矩陣括號告訴我們先算誰。舉個能直接跑的例子3 10 30 30 5 5 60 (A(BC))這個例子里A 是 10×30B 是 30×5C 是 5×60計算順序是先算 B 和 C再把結果和 A 相乘。最后輸出的總乘法次數(shù)是 27000而不是 4500。這里的差別我后面會專門講。第一次做這道題的人很容易把三個矩陣的維度關系搞混拿著 10×30、30×5、5×60 三個維度一頓乘最后也不知道自己算的是哪一步的量。順便說一個容易忽略的細節(jié)表達式里的字母順序并不一定和輸入順序完全對應但要對應到第幾個矩陣一般是按 A、B、C 從第一個開始映射。也就是說字母 A 對應第一組行列數(shù)字母 B 對應第二組依次類推。別看這個映射簡單實際寫代碼的時候很多人會在“字母轉下標”這一步翻車尤其是當題目給的矩陣數(shù)量超過三個的時候。1.2 這個題型的三個隱藏考點第一眼看上去題目只考矩陣乘法規(guī)則其實它把三樣東西揉在了一起。第一是數(shù)學基礎你得知道兩個矩陣相乘時維度怎么匹配、結果維度怎么變第二是數(shù)據結構括號嵌套天然適合用棧來處理第三是工程細節(jié)比如字符串讀取、空行、溢出、邊界條件。這三樣只要有一個沒處理好提交就會 WA。為什么華為機考喜歡這種題因為它的區(qū)分度很微妙。你給一個完全沒準備的人他也能寫出一個看似正確的循環(huán)但一跑樣例就錯你給一個準備工作做得好的人五分鐘就能把核心邏輯寫完剩下的時間都在做自測用例。這種題不是靠背模板就能蒙混過關的它要求你真的理解每一步在算什么。我甚至覺得它比一些表面復雜的圖論題更適合當機考試題因為代碼量少錯誤卻非常隱蔽。我見過一個很典型的錯誤寫法有人只用了一個變量記錄總次數(shù)遇到右括號就隨手彈棧卻沒有把中間結果的維度塞回棧里。這么寫在小樣例上可能碰巧對一旦表達式變成三層括號嵌套立刻全亂。所以刷這道題重點不是背代碼而是把“棧里到底存的是什么”想明白。2. 計算量從哪來矩陣乘法的規(guī)則和維度更新2.1 單個乘法的“性價比”公式復習一下基礎。一個 m×n 的矩陣和一個 n×p 的矩陣相乘前提是左邊矩陣的列數(shù)必須等于右邊矩陣的行數(shù)結果矩陣是 m×p。運算的時候結果矩陣里的每一個元素都要做一個長度為 n 的點積點積里包含 n 次乘法和 n-1 次加法。所以整個乘法過程會執(zhí)行 m×p×n 次標量乘法。在機考里題目說的“計算量估算”通常指的就是標量乘法次數(shù)。為什么只看乘法不看加法因為矩陣乘法里乘法的耗時通常占主導地位而且機考題目為了簡化模型一般就直接讓你統(tǒng)計乘法次數(shù)。你可以把它理解成一個“性價比公式”一次矩陣相乘的代價等于左矩陣的行數(shù)×左矩陣的列數(shù)×右矩陣的列數(shù)。比如 A 是 10×20B 是 20×30那么 A×B 的代價就是 10×20×306000結果矩陣是 10×30。這里有一個特別容易踩的坑結果矩陣的維度是左矩陣行數(shù)和右矩陣列數(shù)。很多人計算完代價以后就忘了更新維度直接把原來的兩個矩陣都丟回棧里。這樣到了下一個括號層級維度信息完全是錯的。后面我會在代碼部分重點強調這件事。2.2 括號順序不同計算量能差六倍矩陣乘法滿足結合律但不滿足交換律。也就是說 (A×B)×C 和 A×(B×C) 結果矩陣是一樣的但中間的計算量可能差很多。這是這類題最核心的理論背景。同樣用上面的例子A 是 10×30B 是 30×5C 是 5×60。如果先算 A×B代價是 10×30×51500得到 10×5 的結果矩陣再和 C 相乘代價是 10×5×603000總代價 4500。如果先算 B×C代價是 30×5×609000得到 30×60 的中間矩陣再和 A 相乘代價是 10×30×6018000總代價 27000。計算順序第一步代價第二步代價總計算量(AB)C10×30×5150010×5×6030004500A(BC)30×5×60900010×30×601800027000看見沒有同一個矩陣序列只是換了個括號位置計算量差了六倍。所以題目里給的那串括號并不是裝飾品它決定了你每一步先合并哪兩個矩陣。這也是為什么這道題不能用“把所有維度乘起來”這種粗暴做法必須嚴格模擬表達式指定的計算順序。2.3 這里說的“估算”到底在算什么很多第一次接觸這道題的人會疑惑“估算”是不是意味著只要算個大概就行完全不是。機考里的“估算”指的是在不模擬具體數(shù)字運算的前提下通過維度推導出理論計算次數(shù)這個結果必須是精準的整數(shù)。這個“估算”和實際機器跑一遍的過程是嚴格對應的。你每合并兩個矩陣付出的代價就是一次完整矩陣乘法的代價。把所有嵌套步驟的代價累加起來就是整個乘法鏈的計算量。你可以把它想象成做賬每一筆矩陣乘法都記一筆賬最后把賬單加總。理解了這一點你就應該明白為什么棧能起作用了。矩陣乘法的計算順序本質上是一個帶括號的表達式求值過程而帶括號的表達式求值棧是最順手的工具。它不是這道題唯一能用的方法卻是代碼最簡單、最不容易出邏輯錯誤的方法。3. 我用棧做完這題的全過程附 Python/C 代碼3.1 為什么棧能完美貼合括號結構括號表達式的核心規(guī)律是越靠里的括號越先算后遇到的右括號對應著最近遇到的左括號這正好是“后進先出”。所以用棧來模擬計算順序思路非常自然遇到字母就把矩陣維度壓棧遇到右括號就彈出兩個矩陣合并它們再把這個中間結果壓回棧里。用棧還有一個額外好處你不用手動維護“當前括號層級”。遞歸當然也能做但是遞歸在處理嵌套層級特別深的長字符串時可能會出現(xiàn)函數(shù)調用棧過深的問題。機考環(huán)境一般不會故意卡你遞歸但用迭代的棧更穩(wěn)時間開銷也更低。這道題的復雜度是 O(n len(expr))遍歷一遍輸入就結束不用動態(tài)規(guī)劃。3.2 Python 版實現(xiàn)代碼下面是我在實際機考風格環(huán)境下常用的 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()這段代碼的核心邏輯只有三件事。第一括號不處理只負責把字母壓棧和把右括號當作合并觸發(fā)點。第二每次遇到右括號彈兩個維度對出來左邊是棧里的倒數(shù)第二個右邊是棧頂那個。第三計算代價以后把結果矩陣的維度壓回去供外層繼續(xù)使用。3.3 C 版實現(xiàn)代碼如果你習慣用 C 刷題可以參考下面這版。要注意的地方和 Python 一樣但 C 里更明顯的問題是數(shù)據類型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; vectorpairlong long, long long dims(n); for (int i 0; i n; i) { cin dims[i].first dims[i].second; } string expr; cin expr; stackpairlong 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))來手動走一遍。初始矩陣A10×30B30×5C5×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)循環(huán)結束?？偞鷥r 9000 18000 27000。這和前面表格里的結果完全一致。你可能會問最后為什么不用管 (10,60)因為一個結果矩陣本身不會再和別人相乘了整個過程已經閉環(huán)。3.5 沒有括號的“線性順序”怎么兜底有些變體題目最后一行可能是一個完全不帶括號的字符串比如ABC。這種情況下計算順序被約定為從左到右先算 A×B再把結果和 C 乘。如果你的代碼只在遇到右括號時才合并最后棧里會堆著三個維度對什么都不會輸出。所以我代碼里加了一個 while 循環(huán)處理“表達式遍歷結束后棧中還剩多個矩陣”的情況。它在棧里從底到頂?shù)胤磸蛷棾鰞蓚€維度對合并等價于線性從左到右的乘法順序。如果輸入本身就是完整括號表達式那么遍歷結束時棧里必然只剩一個矩陣這個 while 循環(huán)不會進去不會產生副作用。這樣加一層兜底代碼的通用性會好很多也不容易因為題目變體而失分。機考平臺上很多自稱“真題”的題目細節(jié)可能和原版有出入多做一層保護沒有壞處。4. 我踩過的坑和排查方法4.1 彈出順序一錯后面每題都廢這道題最經典的問題就是左右矩陣搞反。假設棧里底部是 A頂部是 B表達式是(AB)正確的做法是先彈出 rightB再彈出 leftA然后按 left×right 的順序計算代價。但很多人會順手寫成先彈出 A再彈出 B結果把 A 當成右矩陣B 當成左矩陣。這兩個順序對代價的影響有多嚴重還是用 A10×30B30×5 來算。正確代價是 10×30×51500。如果順序反了你會拿 B 的行 30 和 B 的列 5 去乘 A 的列 30得到 30×5×304500。題目可能只讓你輸出數(shù)字不會提醒你錯在矩陣方向所以這個錯誤非常隱蔽。我的經驗是寫代碼時不要依賴“我記著是彈出 right 再彈出 left”而是在注釋里明確寫清楚棧頂是右操作數(shù)棧頂下面是左操作數(shù)。這樣每次寫回來都不會再犯迷糊。4.2 中間結果維度必須塞回棧里第二高頻的錯誤是算完兩個矩陣相乘以后忘了把結果矩陣的維度更新回棧里。比如算完 B×C得到的是 30×60 的矩陣不是原來的 30×5也不是 5×60。如果你把其中隨便一個原維度壓回去下一層括號繼續(xù)合并時算出來的代價就會離譜。這個問題在表達式嵌套只有一層時不會暴露因為處理完最內層括號程序就結束了。但是一旦表達式是A(B(C(D)))這種多層嵌套每層都要依賴上一層的結果維度錯誤會逐層放大。我見過有人第一層結果就錯了后面雖然邏輯沒問題但答案能從幾萬錯到幾百萬。我自己后來養(yǎng)成一個習慣每完成一次彈棧合并立刻在草稿紙上寫一遍此時棧里的內容。寫代碼前先手推兩個不同的樣例能擋住絕大多數(shù)維度更新錯誤。4.3 讀取輸入的兩種寫法差別很大機考環(huán)境里輸入讀取是最容易被忽略的環(huán)節(jié)。逐行調用input()或readline()沒問題但一旦測試用例在最后一行表達式后面有多余的空行或者表達式和前面的維度數(shù)據之間出現(xiàn)奇怪的空白字符逐行讀取就可能出錯。我更喜歡一次性把整個輸入讀完再用 split 切分 token。這樣做的好處是不管中間有多少空白行程序都能自適應。需要注意的是表達式這一項可能被 split 切成多個 token比如( A ( B C ) )這種帶空格的寫法所以要用.join(data[idx:])把它們拼回去。別小看這一行它能讓代碼在格式不太規(guī)范的測試數(shù)據下照樣跑對。4.4 計數(shù)類型與溢出問題矩陣乘法計算量的增長速度比你想象中快。假設一個矩陣鏈有幾十個矩陣每個維度都是幾百那么一次乘法的代價就是幾千萬累計起來很容易突破 int 的范圍。C 里用 int 保存 total會在極端數(shù)據下溢出成負數(shù)Java 里用 int 同理。Python 的整數(shù)是任意精度的所以沒有這個問題但 C 和 Java 一定要用 long long。我建議在 C 代碼里把所有維度也一并聲明為 long long。這樣計算left.first * left.second * right.second時不會因為中間結果先按 int 運算而溢出再賦給 long long 時已經來不及了。這個細節(jié)在機考環(huán)境里就是白送的得分點別讓它丟。4.5 別和矩陣鏈動態(tài)規(guī)劃混為一談有些人在準備這道題之前可能先看過更經典的“矩陣鏈乘法最優(yōu)括號化”問題那道題的目標是求最小計算量解法是區(qū)間動態(tài)規(guī)劃。于是一看到“矩陣乘法計算量”幾個字就直接背 DP 模板結果寫了一大堆代碼輸出卻和題目要求的對不上。核心區(qū)別在于動態(tài)規(guī)劃題讓你在“所有可能的括號方案”里挑最優(yōu)的機考這道題直接給你指定了括號順序讓你去模擬它。有種情況需要額外注意如果題目真的問了“最小乘法次數(shù)”或者“求最優(yōu)計算順序”那才切回動態(tài)規(guī)劃。當前這道題的名字是“計算量估算”不是“最小計算量”看到輸入里的括號表達式就該秒選棧解法。5. 考試前怎么把它練成穩(wěn)定拿分題5.1 自測樣例集5 分鐘驗證自己代碼我練這道題的時候會準備一組覆蓋各種邊界情況的自測樣例。建議你也照這個思路來不要只跑題目給的那一兩個樣例。第一組單矩陣無乘法輸入 n1表達式A輸出 0。這一步能驗證程序不會在棧為空時崩潰。第二組兩個矩陣直接相乘例如A是 10×20B是 20×30表達式(AB)輸出 6000。第三組前面反復提到的三層矩陣比較(AB)C和A(BC)的輸出確認順序影響計算量。第四組多層嵌套表達式比如A(B(C(D)))重點檢查中間結果維度更新。第五組無括號表達式ABC驗證 while 兜底邏輯。測試數(shù)據期望輸出n1, A5×5, 表達式 A0n2, A10×20, B20×30, 表達式 (AB)6000n3, A10×30, B30×5, C5×60, 表達式 A(BC)27000n3, 同上, 表達式 (AB)C4500n3, 同上, 表達式 ABC4500這些用例能覆蓋絕大多數(shù)邏輯盲區(qū)。如果跑完這五組都沒問題基本可以放心提交。5.2 考場時間拆解與代碼風格建議這道題正常難度下讀題加寫代碼加自測控制在 15 分鐘以內是比較合理的。如果超過 25 分鐘還沒跑通過大概率是對棧的模擬過程產生了混淆建議先在紙上畫一遍棧的變化再繼續(xù)改代碼而不是盲改。代碼風格方面我強烈建議變量名不要用 a、b、c 這種含義不明的縮寫。機考環(huán)境里沒人看你的代碼但你自己調試時會看。left、right、rows、cols這種命名能幫你迅速定位問題。另外在計算代價前加一行注釋寫明“代價 左矩陣的行數(shù) × 左矩陣的列數(shù) × 右矩陣的列數(shù)”能有效防止自己臨時想岔。5.3 一個可以復用的基礎 IO 處理模板我后來把這類題的輸入讀取封裝成了一個固定模板刷機考題時直接復用。它的邏輯是整個輸入讀進來按空白切割第一個 token 是 n往后取 2n 個數(shù)字作為矩陣維度剩余部分用拼接恢復成表達式。這個模板對很多“先給數(shù)量再給一組數(shù)據最后給表達式/查詢串”的題型都適用。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 和算法邏輯分開調試的時候會更清晰。我個人體會是這類代碼量很小的題真正吃時間的往往不是算法本身而是輸入邊界處理。提前準備好模板等于把最容易被扣分的地方提前堵住。矩陣乘法計算量估算這道題值得你在考前靜下心來完整親手寫一遍而不是只看別人的思路。寫明白一次之后以后再遇到帶括號的表達式計算類問題都會覺得順暢很多。