1. 從 1231 這組樣例出發(fā)為什么暴力枚舉會被卡死在信息學(xué)奧賽一本通的動態(tài)規(guī)劃章節(jié)里編號 1275 的【例9.19】乘積最大是一道被無數(shù)人反復(fù)講、又反復(fù)講錯的題。它出自早年的 NOIP 提高組題面樸素得像小學(xué)奧數(shù)給一個長度為 N 的數(shù)字串再給 K 個乘號要求把這 K 個乘號全部插進(jìn)數(shù)字串的縫隙里使分出來的 K1 個部分相乘的結(jié)果最大。這道題的輸入只有兩行輸出只有一個整數(shù)看起來五分鐘就能寫完但真正動手的人很快會發(fā)現(xiàn)兩個問題一是怎么切才最優(yōu)靠人眼試根本試不出來二是當(dāng) N 最大到 40 的時候答案會膨脹到 40 位以上用long long存結(jié)果直接溢出。這篇內(nèi)容我不打算只貼一份代碼就完事。和平常寫題解不一樣我更想把為什么狀態(tài)要這么定義為什么枚舉范圍只能這么取為什么高精度不是可選優(yōu)化而是必需品這幾件事說透。因為把這道題吃下來你順手就能拿下后面一大類區(qū)間決策類的問題投入產(chǎn)出比很高。1.1 三個容易讀漏的題目約束先把題目條件逐條羅列清楚這三條里任何一條看漏代碼都過不了。第一乘號必須恰好用完。題目說的是使用 K 個乘號不是至多 K 個。這意味著分出來的段數(shù)固定是 K1 段每一段至少得有 1 位數(shù)字。這是后面枚舉范圍推導(dǎo)的直接依據(jù)。第二數(shù)字串的長度 N 可能到 40。數(shù)據(jù)范圍大致是 6 ≤ N ≤ 401 ≤ K ≤ 6且 K N。40 位數(shù)字切 7 段最后乘積的量級在 10 的 40 次方上下而long long的極限只有約 9.2 × 10 的 18 次方連尾數(shù)都比不上。所以這道題的正解必須自帶高精度。第三數(shù)字串里可能出現(xiàn) 0。很多人在寫狀態(tài)初值的時候習(xí)慣用-1表示這個狀態(tài)還沒被算過結(jié)果遇到含 0 的數(shù)據(jù)就翻車——因為真實的乘積就是 0跟你用來表示未計算的哨兵值撞車了。這個坑我在后面會單獨說。樣例輸入是4 2加一行1231樣例輸出是62。切法是1 * 2 * 31。你可以自己驗算一下其他兩種切法1 * 23 * 1 2312 * 3 * 1 36確實都不如 62。1.2 讓兩段盡量勻的直覺為什么一定會錯大部分人第一次做這道題腦子里會冒出一個貪心既然要讓乘積最大那讓每一段的數(shù)值盡量接近不就行了這就是小學(xué)里和一定、差越小積越大的直覺。這個直覺在兩個數(shù)的場合是對的但一旦段數(shù)變多、而且還要考慮數(shù)位長度對數(shù)值的影響它就完全失效了。舉個能直接打臉的例子數(shù)字串1119K 1也就是只切一刀。三種切法分別是 1 × 119 119、11 × 19 209、111 × 9 999。按盡量勻的直覺應(yīng)該選 11 × 19 209但真實最優(yōu)是 111 × 9 999差了將近五倍。為什么會這樣因為在這個數(shù)字串里末位那個 9 是唯一的大數(shù)因子把它單獨切出來當(dāng)乘數(shù)收益遠(yuǎn)大于讓兩段位數(shù)接近。數(shù)字的大小是由高位主導(dǎo)的而位數(shù)接近只是看起來勻跟數(shù)值均衡完全是兩碼事。更有意思的是同一組數(shù)字串在不同 K 下最優(yōu)切點會跳到完全不同的位置。還是1231K 1 時最優(yōu)是12 * 31 372切在中間K 2 時最優(yōu)卻是1 * 2 * 31 62切在靠前的位置。同一串?dāng)?shù)字乘號個數(shù)一變最優(yōu)結(jié)構(gòu)就變了。這就說明不存在一個固定的貪心規(guī)則能覆蓋所有情況必須老老實實做決策搜索。1.3 枚舉所有切法的代價C(39,6) 不是一個小數(shù)字有人會想那我把所有切法枚舉一遍不就行了N 40 的時候一共有 39 個空隙從中選 K 6 個位置放乘號組合數(shù)是 C(39, 6) 3262623三百多萬種。單看這個數(shù)字好像還在可接受范圍內(nèi)——如果每次切分只需要一次整數(shù)乘法的話確實如此。但問題恰恰在于每一次切分你都要做 6 次高精度乘法而每個大數(shù)可能有 40 位左右。手寫大數(shù)乘法是 O(L2) 的L ≈ 40一次就是 1600 次基本運算6 次乘法加起來接近一萬次?？傔\算量大約是 3262623 × 10000 ≈ 3.3 × 10 的 10 次方這個量級在競賽的 1 秒時限里是絕對過不去的。而用動態(tài)規(guī)劃來做需要執(zhí)行的乘法次數(shù)只有幾千次——具體來說是三層循環(huán)枚舉狀態(tài)和決策點的組合數(shù)大概是 K × N2 / 2 ≈ 4800 次。從三千萬次運算降到五千次這就是為什么這道題必須用 DP而不是靠枚舉加剪枝硬扛。2. dp[i][j] 這個狀態(tài)不是拍腦袋定的動態(tài)規(guī)劃最難的從來不是寫轉(zhuǎn)移方程而是想清楚狀態(tài)該怎么定義。很多人背下了這道題的dp[i][j]表示前 i 個數(shù)字里插 j 個乘號但問他為什么這么定答不上來。我把自己當(dāng)初推導(dǎo)的過程完整復(fù)述一遍希望能幫你建立狀態(tài)是被問題結(jié)構(gòu)逼出來的這種感覺。2.1 決策動作到底是選數(shù)字還是切位置很多人一看到乘積最大第一反應(yīng)是把狀態(tài)定義成選到第幾個數(shù)字為止然后糾結(jié)于這個數(shù)字到底屬于哪一段。這就是走偏了。重新讀一遍題目數(shù)字串的順序是不能打亂的你能做的唯一動作就是在某些縫隙里插入乘號。所以真正意義上的決策是第 i 個數(shù)字后面到底切不切。換句話說問題的解是一組切分位置的集合而不是一組數(shù)字的排列。一旦意識到?jīng)Q策對象是切分點狀態(tài)的形狀就清晰了我們需要記錄的核心信息是已經(jīng)處理到了數(shù)字串的第幾位以及已經(jīng)用掉了幾個乘號。前者決定了還剩哪些數(shù)字可用后者決定了還剩幾個乘號要放。這兩個維度合起來就組成了dp[i][j]。2.2 為什么按前綴長度的劃分天然滿足無后效性動態(tài)規(guī)劃能不能成立關(guān)鍵看狀態(tài)轉(zhuǎn)移有沒有后效性。所謂無后效性就是一旦到達(dá)某個狀態(tài)未來的決策只跟這個狀態(tài)本身有關(guān)跟你是怎么走到這里的無關(guān)。對于這道題dp[i][j]表示把前 i 個數(shù)字分成 j1 段的最大乘積。注意這里的關(guān)鍵點前 i 個數(shù)字被劃分成 j1 段之后后面剩下的數(shù)字串第 i1 位到第 N 位該怎么切跟前面這 j1 段具體是怎么分的沒有關(guān)系。因為你只需要知道前面那部分的最大乘積是多少后面部分的最優(yōu)切法不受影響它們之間唯一的耦合就是乘起來這個動作。這就滿足了最優(yōu)子結(jié)構(gòu)全局最優(yōu)解一定能拆成一個前綴最優(yōu)解乘上一段后綴數(shù)字。反過來說如果你把狀態(tài)定義成第 i 個數(shù)字所在的段是從第幾位開始的那狀態(tài)的維度就爆炸了而且也不滿足無后效性因為后續(xù)切分要依賴的具體分段信息太多了。2.3 初始化dp[i][0] 與無解狀態(tài)的處理選擇狀態(tài)定好之后邊界條件就順理成章了。dp[i][0]表示前 i 個數(shù)字里一個乘號都不放那就只有一個段值就是前 i 位數(shù)字組成的那個整數(shù)。比如樣例里的1231dp[1][0] 1dp[2][0] 12dp[3][0] 123dp[4][0] 1231。這個初始化用高精度直接對字符串切片轉(zhuǎn)換就行非常直觀。至于無解狀態(tài)有兩種常見寫法。一種是把整個 dp 數(shù)組初始化為 0因為乘積的最小可能值就是 00 作為一個合法的當(dāng)前最大候選值不會造成任何錯誤——任何正數(shù)都會把它頂?shù)舳绻泻蜻x都算出來是 0那說明數(shù)字串里全是 0答案本來就是 0。另一種是初始化為 -1 當(dāng)作哨兵轉(zhuǎn)移時特判。我強(qiáng)烈建議第一種理由很實在這題的乘積天然是非負(fù)的0 本身就是合法值域的下界用它當(dāng)初始值既省代碼又不會誤判而 -1 哨兵反而會在含 0 的數(shù)據(jù)上制造歧義。這里還有個容易忽略的細(xì)節(jié)dp[i][j]只對 j i 有意義。因為要把前 i 個數(shù)字切成 j1 段每段至少 1 位所以必須滿足 i ≥ j1。對于 i ≤ j 的狀態(tài)我們根本不會去訪問也就不用管。3. 轉(zhuǎn)移方程里枚舉點 t 的上下界寫錯一個就 WA轉(zhuǎn)移方程本身不長但那個枚舉變量的取值范圍是這道題最容易寫錯的地方。我見過太多人把下界寫成 1結(jié)果要么數(shù)組越界要么算出莫名其妙的答案。3.1 把最后一段單獨拎出來推導(dǎo)轉(zhuǎn)移方程的標(biāo)準(zhǔn)姿勢是思考最后一步做了什么決策。當(dāng)我們計算dp[i][j]前 i 個數(shù)字插 j 個乘號分成 j1 段時考慮最后一個乘號插在哪里。假設(shè)它插在第 t 個數(shù)字之后那么整個串就被切成了兩部分前面是前 t 個數(shù)字后面是從第 t1 位到第 i 位的這一段。前面那部分需要插 j-1 個乘號也就是dp[t][j-1]后面那部分是固定的一個整數(shù)記為num(t1, i)。于是轉(zhuǎn)移方程就是dp[i][j] max{ dp[t][j-1] * num(t1, i) }對所有合法的 t 取最大值這里的num(t1, i)表示數(shù)字串從第 t1 位到第 i 位組成的那個整數(shù)。整個思路就是把最后一段的起點在哪里枚舉一遍這是所有區(qū)間分割類 DP 的通用套路。3.2 下界為什么是 j 而不是 1現(xiàn)在來說枚舉范圍。t 的取值范圍必須是[j, i-1]這兩個邊界都有明確的現(xiàn)實含義。先說下界 t ≥ j。因為dp[t][j-1]要求把前 t 個數(shù)字分成 j 段插 j-1 個乘號而分成 j 段至少需要 j 個數(shù)字。如果 t j這個狀態(tài)根本沒有意義強(qiáng)行訪問會讀到未初始化的垃圾值在 C 里就是默認(rèn)的 0會讓答案偏小。這就是為什么下界是 j而不是想當(dāng)然的 1。再說上界 t ≤ i-1。因為最后一段num(t1, i)至少要包含 1 位數(shù)字所以 t 最多到 i-1。如果寫成 t ≤ i那就切出一段空的num(i1, i)在字符串上是個非法區(qū)間轉(zhuǎn)換出來直接錯。順帶說一句外層循環(huán)的順序必須是先枚舉 j再枚舉 i。因為dp[i][j]依賴的是dp[t][j-1]也就是乘號個數(shù)少一層的狀態(tài)。只有當(dāng)所有 j-1 層的結(jié)果都算完了才能算第 j 層。3.3 手推 1231 的完整 DP 表光看公式還是虛我們拿樣例1231、K 2 手動跑一遍把整張表填出來。數(shù)字串各位分別是 1、2、3、1。先算所有區(qū)間數(shù)值num(1,1)1num(2,2)2num(3,3)3num(4,4)1num(1,2)12num(2,3)23num(3,4)31num(1,3)123num(2,4)231num(1,4)1231。i前 i 位dp[i][0]dp[i][1]dp[i][2]11——2122—31233664123137262逐格解釋一下第 1 層j 1的計算dp[2][1]t 只能取 1dp[1][0] * num(2,2) 1 * 2 2。dp[3][1]t 取 1 得1 * num(2,3) 1 * 23 23t 取 2 得dp[2][0] * num(3,3) 12 * 3 36。取最大值 36。dp[4][1]t 取 1 得1 * 231 231t 取 2 得12 * 31 372t 取 3 得123 * 1 123。取最大值 372。再看第 2 層j 2注意此時 t 的下界是 2dp[3][2]t 只能取 2dp[2][1] * num(3,3) 2 * 3 6。dp[4][2]t 取 2 得dp[2][1] * num(3,4) 2 * 31 62t 取 3 得dp[3][1] * num(4,4) 36 * 1 36。取最大值 62。最終答案dp[4][2] 62跟樣例輸出完全對上。把這個表親手推一遍比看十遍方程都管用——你能親眼看到 t 的下界是怎么隨著 j 往上走的。4. 40 位數(shù)字的乘積有多大高精度不是可選項前面提到高精度這里展開講清楚為什么這道題繞不過去以及手寫大數(shù)到底要寫哪些東西。4.1 量級估算為什么 long long 一定會炸先做一個粗算讓你對答案的大小有個概念。N 40、K 6也就是把 40 位數(shù)字切成 7 段。根據(jù)分段越均勻乘積越大的規(guī)律這個是針對位數(shù)成立的經(jīng)驗規(guī)律和前面說的數(shù)值均衡不一樣7 段大致是每段 5 到 6 位。假設(shè)數(shù)字串里全是 940 位切 7 段比較合理的分法是 6666655 40。每段的數(shù)值大概在 10 的 5 次方到 10 的 6 次方之間7 段乘起來量級大約是 10 的 40 次方左右。這意味著答案有 40 位左右的十進(jìn)制數(shù)字。long long能表示的最大值約是 9.22 × 10 的 18 次方也就是 19 位十進(jìn)制數(shù)。兩者差了二十多個數(shù)量級用long long存這個答案連中間過程都走不完第一次乘法就會溢出成負(fù)數(shù)或者垃圾值。4.2 C 手寫大數(shù)乘法與比較的骨架C 沒有任何內(nèi)置大數(shù)必須手寫。好在這道題只需要兩個操作大數(shù)乘大數(shù)和大數(shù)比較大數(shù)。我一般用低位在前的數(shù)組存十進(jìn)制位也就是d[0]存?zhèn)€位d[1]存十位以此類推。這樣進(jìn)位的時候從下標(biāo) 0 往大走寫起來最順手。大數(shù)比較的邏輯很簡單先比位數(shù)位數(shù)多的更大位數(shù)相同就從高位往低位逐位比第一位不同的誰大誰就大。這里有個非常經(jīng)典的錯誤就是只寫位數(shù)不同時比位數(shù)位數(shù)相同就返回相等——位數(shù)相同但數(shù)值不同的情況多了去了比如 1234 和 4321 都是 4 位必須逐位比較才能分出大小。大數(shù)乘法的核心是模擬豎式兩層循環(huán)把d[i] * d[j]累加到結(jié)果的第ij位上等所有位都累加完再從低位到高位統(tǒng)一處理進(jìn)位。中間累加用的數(shù)組要開得足夠大長度份應(yīng)該是兩個乘數(shù)位數(shù)之和再加 2。關(guān)于中間值會不會溢出這里可以放心每一位的乘積最大是 9 × 9 81而同一位置上最多累加 40 次也就是 3240 左右int完全裝得下。所以中間數(shù)組用int就夠不需要long long。從字符串轉(zhuǎn)大數(shù)也有個小講究。我習(xí)慣用逐位乘 10 加當(dāng)前位的方式從左到右掃字符串每讀一位就把當(dāng)前大數(shù)整體乘 10 再加上這一位的數(shù)字。這個過程中要用一個carry變量從低位往高位傳遞邏輯和乘法進(jìn)位一樣。特別注意全為 0 的輸入因為 0 乘 10 還是 0沒有產(chǎn)生任何進(jìn)位數(shù)組長度會一直是 0必須特判——如果掃完了長度還是 0就把值設(shè)成 0、長度設(shè)成 1。4.3 Python 與 Java 的降維寫法如果你只是想把這道題的思路搞明白而不是非得在 C 里手寫高精度那用 Python 寫這道題簡直是降維打擊。Python 的整數(shù)是任意精度的int直接就能存 40 位、甚至 1000 位的數(shù)乘法和比較都是原生支持的。同樣一段 DP 邏輯Python 版本連大數(shù)類都不用寫字符串轉(zhuǎn)整數(shù)直接int(s[i-1:j])搞定十幾行代碼就能 AC。Java 的話java.math.BigInteger提供了multiply和compareTo兩個方法也能省掉手寫高精度的功夫只是寫起來比 Python 啰嗦一些。不過我還是建議你至少手寫一遍 C 版本。原因很現(xiàn)實競賽的默認(rèn)語言還是 C遇到真正卡高精度的題目你總得會寫。Python 版本適合用來驗證你的 DP 邏輯對不對——如果 Python 過了而 C 不過那問題一定出在高精度實現(xiàn)上排查方向一下子就清晰了。這里補(bǔ)充一句復(fù)雜度分析方便你判斷自己的實現(xiàn)會不會超時。整個 DP 的乘法調(diào)用次數(shù)約為 K × N2 / 2在 K 6、N 40 時大約是 4800 次每次大數(shù)乘法是 O(L2)L 最多 80 位左右也就是幾千次基本運算。乘起來大概三千多萬次基本操作在 C 里是毫秒級的完全不用擔(dān)心性能。5. 完整代碼與調(diào)試現(xiàn)場我在下標(biāo)上栽的三個跟頭代碼我給兩個版本C 的手寫高精度版和 Python 的直球版。給完之后重點說說我當(dāng)年調(diào)試時踩過的坑這幾處比代碼本身更值錢。5.1 C 版本數(shù)組存大數(shù) 手寫乘法#include bits/stdc.h using namespace std; const int MAXL 105; struct Big { int d[MAXL]; // d[0] 是個位下標(biāo)越大位權(quán)越高 int len; Big() { memset(d, 0, sizeof(d)); len 1; } // 默認(rèn)值是 0 }; // 把 s[l..r] 轉(zhuǎn)成大數(shù)下標(biāo)從 0 開始閉區(qū)間 Big toBig(const string s, int l, int r) { Big a; a.len 0; for (int i l; i r; i) { int carry s[i] - 0; // a a * 10 當(dāng)前位 for (int j 0; j a.len; j) { int t a.d[j] * 10 carry; a.d[j] t % 10; carry t / 10; } while (carry 0) { a.d[a.len] carry % 10; carry / 10; } } if (a.len 0) { a.d[0] 0; a.len 1; } // 全 0 的特判 return a; } Big mul(const Big a, const Big b) { Big c; if ((a.len 1 a.d[0] 0) || (b.len 1 b.d[0] 0)) return c; int tmp[MAXL * 2] {0}; for (int i 0; i a.len; i) for (int j 0; j b.len; j) tmp[i j] a.d[i] * b.d[j]; int len a.len b.len 1; for (int i 0; i len; i) { tmp[i 1] tmp[i] / 10; tmp[i] % 10; } while (len 1 tmp[len - 1] 0) --len; c.len len; for (int i 0; i len; i) c.d[i] tmp[i]; return c; } bool bigger(const Big a, const Big b) { // a b 嗎 if (a.len ! b.len) return a.len b.len; for (int i a.len - 1; i 0; --i) if (a.d[i] ! b.d[i]) return a.d[i] b.d[i]; return false; } int n, k; string s; Big dp[45][10]; Big num[45][45]; int main() { cin n k; cin s; for (int i 0; i n; i) for (int j i; j n; j) num[i][j] toBig(s, i, j); for (int i 1; i n; i) dp[i][0] num[0][i - 1]; for (int j 1; j k; j) for (int i j 1; i n; i) for (int t j; t i - 1; t) { Big cand mul(dp[t][j - 1], num[t][i - 1]); if (bigger(cand, dp[i][j])) dp[i][j] cand; } for (int i dp[n][k].len - 1; i 0; --i) cout dp[n][k].d[i]; cout \n; return 0; }代碼里num[t][i-1]這個下標(biāo)最容易看暈dp里用的是前 i 位這種 1 起始的計數(shù)而num數(shù)組和字符串都是 0 起始的。前 i 位對應(yīng)字符串下標(biāo)0..i-1前 t 位對應(yīng)0..t-1所以最后一段就是從下標(biāo) t 到 i-1寫成num[t][i-1]。這個問題我在下一節(jié)會專門說。5.2 Python 版本n, k map(int, input().split()) s input().strip() # num[i][j]第 i 位到第 j 位組成的整數(shù)1 起始的閉區(qū)間 num [[0] * (n 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(i, n 1): num[i][j] int(s[i - 1:j]) dp [[0] * (k 1) for _ in range(n 1)] for i in range(1, n 1): dp[i][0] num[1][i] for j in range(1, k 1): for i in range(j 1, n 1): for t in range(j, i): dp[i][j] max(dp[i][j], dp[t][j - 1] * num[t 1][i]) print(dp[n][k])兩邊對照著看能明顯感覺到 Python 把所有高精度的臟活都藏起來了剩下的骨架跟 C 一模一樣。建議你先用 Python 把邏輯跑通再用 C 重寫一遍這樣調(diào)試的時候能確定問題到底是出在算法還是出在高精度實現(xiàn)上。5.3 三個真實踩坑記錄坑一num 數(shù)組的下標(biāo)基準(zhǔn)混用。我當(dāng)初寫 C 版本的時候dp用的是 1 起始前 i 位結(jié)果在取最后一段的時候順手寫成了num[t 1][i]按照 Python 那套 1 起始的約定來寫的。但 C 里num存的是 0 起始的字符串切片num[t1][i]實際取到的是從下標(biāo) t1 到 i 的內(nèi)容正好錯開了一位。表現(xiàn)就是樣例能過因為位數(shù)少錯位不太明顯但交上去大面積 WA。這種錯誤的排查方法很簡單打印中間狀態(tài)把所有dp[i][0]打出來跟手算的前綴數(shù)值對一下一眼就能看出來錯位?？佣髷?shù)比較只比長度。這是我見過最高頻的高精度錯誤。很多人寫比較函數(shù)的時候圖省事只寫了if (a.len ! b.len) return a.len b.len; return false;長度相同就直接認(rèn)為相等。這在本題里會直接導(dǎo)致答案偏小因為兩個位數(shù)相同的候選乘積會互相頂?shù)糇詈罅粝碌目赡懿皇钦嬲畲蟮哪莻€。正確寫法必須是長度相同時逐位從高位往下比?？尤朔ㄖ虚g數(shù)組沒清空、或者開小了。中間數(shù)組tmp每次調(diào)用乘法都要重新清零如果把它寫成全局變量或者static上一次的結(jié)果會殘留下來污染這一次的計算。另外數(shù)組長度也要留夠兩個 40 位大數(shù)相乘結(jié)果最多 80 位進(jìn)位之后可能到 81 位所以我習(xí)慣開MAXL * 2也就是 210穩(wěn)一點。還有一個不算坑但值得提的點輸出大數(shù)的時候千萬別忘了逆序。因為數(shù)組是低位在前的d[0]是個位輸出必須從len-1往下走到 0。寫成從 0 到len-1輸出的話你會看到一個數(shù)字完全反過來的答案。6. 換個問法這道題還能怎么變形把這道題的正解寫出來只是第一步。真正讓這道題的價值翻倍的是它背后那一套區(qū)間分割 決策枚舉的思維能直接遷移到一大批變體上。這里挑幾個最有代表性的說說。6.1 至多 K 個乘號多一層取 max 就夠如果題目改成至多使用 K 個乘號答案就不是dp[n][K]了而是max(dp[n][0], dp[n][1], ..., dp[n][K])。為什么因為多用一個乘號并不總是更好。舉個極端的例子數(shù)字串10、K 1切一刀得到1 * 0 0不切得到10。顯然不切更優(yōu)。原因是數(shù)字串里出現(xiàn)了 0任何跟 0 相乘的段都會把整個乘積拉成 0。所以遇到至多這種表述最后答案要在一個維度上再掃一遍取最大值。這個改動只有幾行但如果不注意題目到底是恰好還是至多就會直接 WA。6.2 要求輸出切分方案加一個決策點數(shù)組有些變體會要求你不只輸出最大乘積還要輸出具體的切分方式比如在第幾位后面插乘號。這時候只需要在原來的轉(zhuǎn)移里多記一個數(shù)組pre[i][j]表示計算dp[i][j]時選中的那個最優(yōu) t 是多少。轉(zhuǎn)移的時候只要發(fā)現(xiàn)當(dāng)前候選值比dp[i][j]大就順手把pre[i][j] t記下來。最后從pre[n][K]出發(fā)往前回溯記t pre[n][K]那么最后一個乘號插在第 t 位后面接著跳到狀態(tài)dp[t][K-1]取pre[t][K-1]以此類推直到乘號用完?；厮莩鰜淼奈恢眯蛄蟹催^來輸出就是完整的切分方案。這個技巧的通用性極強(qiáng)幾乎所有輸出方案的 DP 題都是這個套路多開一個數(shù)組記錄我是從哪個狀態(tài)轉(zhuǎn)移過來的。6.3 和石子合并矩陣連乘的家族關(guān)系如果你做過經(jīng)典的石子合并或者矩陣連乘應(yīng)該會有種熟悉感。那類題的狀態(tài)是f[i][j]表示把第 i 堆到第 j 堆合并成一堆的最小代價枚舉的是最后一次合并的分界點 k轉(zhuǎn)移形如f[i][j] min(f[i][k] f[k1][j] 代價)。乘積最大這道題的結(jié)構(gòu)其實是一樣的枚舉最后一段的起點只不過這道題的左半部分是從串首開始的前綴而不是任意區(qū)間。之所以有區(qū)別是因為石子合并要合并成一個整體所以左右兩部分都是中間區(qū)間的形式而乘積最大的最終結(jié)果是一條從前到后的完整劃分所以左邊的狀態(tài)天然就是前綴。理解了這個同構(gòu)關(guān)系你會發(fā)現(xiàn)一大類題都能用同一套思考框架去套確定決策動作 → 確定狀態(tài)維度 → 推出轉(zhuǎn)移時枚舉的分界點 → 確定邊界和初始化 → 處理數(shù)值溢出和精度。這套流程走順了區(qū)間 DP 這一類題基本就通了。我個人在實際刷題過程中的體會是像 1275 這種看起來簡單的老題其實是最值得反復(fù)琢磨的。它把狀態(tài)定義枚舉邊界高精度這三個動態(tài)規(guī)劃的核心考點全揉在一起了每一處都能踩坑每一處也都能學(xué)到東西。第一次寫不出來很正常把樣例的那張 DP 表親手推兩遍再對著代碼單步走一遍這道題就真正變成你自己的了。