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