1. 項(xiàng)目概述從“藍(lán)肽子序列”看國賽動(dòng)態(tài)規(guī)劃命題邏輯看到“藍(lán)肽子序列”這個(gè)題目很多參加過藍(lán)橋杯國賽或者正在備賽的同學(xué)可能會(huì)心一笑或者眉頭一緊。這確實(shí)是2020年第十一屆藍(lán)橋杯軟件類國賽C/C/Java組的一道經(jīng)典真題。它不像一些純數(shù)學(xué)題那樣抽象也不像某些模擬題那樣繁瑣而是精準(zhǔn)地卡在了“字符串處理”與“動(dòng)態(tài)規(guī)劃”兩大核心知識點(diǎn)的交匯處。題目名字里的“藍(lán)肽”是個(gè)有趣的包裝本質(zhì)上它考察的是對“最長公共子序列LCS”這一經(jīng)典動(dòng)態(tài)規(guī)劃模型的深刻理解與靈活變通能力。這道題的價(jià)值在哪里對于算法競賽選手而言它是一塊極佳的試金石。國賽級別的題目往往不會(huì)直接考教科書上的裸模板而是會(huì)給經(jīng)典模型披上一層“外衣”需要你剝開現(xiàn)象看本質(zhì)。“藍(lán)肽子序列”正是如此它把字符序列升級成了由大寫字母開頭的“單詞”序列這直接增加了問題的復(fù)雜度也完美地區(qū)分了“只會(huì)背模板”和“真正理解算法”的選手。解決它不僅意味著你能寫出LCS的狀態(tài)轉(zhuǎn)移方程更意味著你掌握了將實(shí)際問題抽象、轉(zhuǎn)化為已知模型的關(guān)鍵思維。在備戰(zhàn)藍(lán)橋杯、CCPC、ICPC等賽事時(shí)這類題目是訓(xùn)練算法思維不可或缺的一環(huán)。2. 核心需求與問題抽象理解“藍(lán)肽”與“子序列”的定義要解決任何問題第一步永遠(yuǎn)是準(zhǔn)確理解題意。我們先把題目中那些帶有生物色彩的術(shù)語“翻譯”成我們熟悉的算法語言。2.1 “藍(lán)肽”是什么——字符串的升級分割題目描述中“藍(lán)肽”是由一個(gè)大寫字母和零個(gè)或多個(gè)小寫字母組成的字符串單元。例如“LanQiaoBei” 這個(gè)字符串按此規(guī)則分割得到的是三個(gè)藍(lán)肽[“Lan”, “Qiao”, “Bei”]。注意分割是確定且唯一的因?yàn)榇髮懽帜傅某霈F(xiàn)標(biāo)志著一個(gè)新藍(lán)肽的開始。核心操作字符串到藍(lán)肽序列的轉(zhuǎn)換。這是解題的第一個(gè)關(guān)鍵步驟。給定一個(gè)字符串s我們需要將其分割成一個(gè)藍(lán)肽數(shù)組或列表peptides。算法很直觀遍歷字符串每當(dāng)遇到一個(gè)大寫字母就標(biāo)志著上一個(gè)藍(lán)肽的結(jié)束如果有的話和當(dāng)前新藍(lán)肽的開始。我們將這個(gè)大寫字母及其后連續(xù)的小寫字母收集起來形成一個(gè)藍(lán)肽加入序列。注意這里有一個(gè)邊界情況需要小心處理即字符串開頭就是大寫字母或者整個(gè)字符串只有一個(gè)藍(lán)肽。在代碼實(shí)現(xiàn)時(shí)初始化一個(gè)空字符串current遍歷時(shí)若當(dāng)前字符是大寫字母且current不為空則將current存入序列然后清空current并加入新的大寫字母若是小寫字母則直接追加到current。遍歷結(jié)束后別忘了將最后一個(gè)current加入序列。2.2 “藍(lán)肽子序列”是什么——LCS模型的變體題目定義如果一個(gè)序列既是序列 S 的藍(lán)肽序列的子序列也是序列 T 的藍(lán)肽序列的子序列那么它就是 S 和 T 的公共藍(lán)肽子序列。這里需要明確兩層“子序列”的概念第一層對原始字符串我們按上述規(guī)則得到了藍(lán)肽序列比如 S 的序列為[S1, S2, S3, ..., Sm] T 的序列為[T1, T2, T3, ..., Tn]。第二層所謂的“藍(lán)肽子序列”指的是從 S 的藍(lán)肽序列中按原順序挑出一些藍(lán)肽可以不連續(xù)同時(shí)這些被挑出的藍(lán)肽按相同順序也出現(xiàn)在 T 的藍(lán)肽序列中。這完全就是最長公共子序列Longest Common Subsequence, LCS問題的定義只不過基本的 LCS 處理的是字符序列而這里處理的是“藍(lán)肽”字符串單元序列。我們的目標(biāo)就是找出兩個(gè)藍(lán)肽序列的最長公共子序列的長度。問題抽象總結(jié) 輸入兩個(gè)由大寫字母開頭的字符串 S 和 T。 處理將 S 和 T 分別分割成藍(lán)肽序列seqS和seqT。求序列seqS和seqT的最長公共子序列的長度。 輸出這個(gè)最大長度。至此一個(gè)看似新穎的題目被我們精準(zhǔn)地抽象為了一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問題。3. 算法核心動(dòng)態(tài)規(guī)劃解最長公共子序列LCS既然本質(zhì)是 LCS那么動(dòng)態(tài)規(guī)劃DP就是標(biāo)準(zhǔn)且最優(yōu)的解法。我們來徹底拆解這個(gè) DP 狀態(tài)的設(shè)計(jì)與轉(zhuǎn)移。3.1 狀態(tài)定義設(shè)dp[i][j]表示考慮序列 S 的前i個(gè)藍(lán)肽seqS[0...i-1]和序列 T 的前j個(gè)藍(lán)肽seqT[0...j-1]它們所能構(gòu)成的最長公共藍(lán)肽子序列的長度。這里使用i和j表示“前多少個(gè)”是為了讓邊界條件即一個(gè)序列為空的情況更容易處理。dp[0][j]和dp[i][0]自然都是 0。3.2 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是 DP 的靈魂它基于對最后一個(gè)元素藍(lán)肽是否被包含在公共子序列中的分類討論當(dāng)seqS[i-1]等于seqT[j-1]時(shí)即當(dāng)前考慮的兩個(gè)藍(lán)肽完全相同。那么這個(gè)藍(lán)肽一定可以貢獻(xiàn)到最長公共子序列中。因此在seqS前i-1個(gè)和seqT前j-1個(gè)的最優(yōu)解基礎(chǔ)上加上這個(gè)匹配的藍(lán)肽。轉(zhuǎn)移方程dp[i][j] dp[i-1][j-1] 1當(dāng)seqS[i-1]不等于seqT[j-1]時(shí)即當(dāng)前兩個(gè)藍(lán)肽不同。那么它們不可能同時(shí)作為公共子序列的最后一個(gè)元素。此時(shí)最長公共子序列要么來自seqS的前i-1個(gè)和seqT的前j個(gè)要么來自seqS的前i個(gè)和seqT的前j-1個(gè)。我們?nèi)烧叩淖畲笾?。轉(zhuǎn)移方程dp[i][j] max(dp[i-1][j], dp[i][j-1])3.3 DP 表格填充與最終答案我們通常會(huì)用一個(gè)二維數(shù)組dp來模擬這個(gè)過程。假設(shè)seqS長度為mseqT長度為n則dp數(shù)組大小為(m1) x (n1)。填充順序由于計(jì)算dp[i][j]需要用到其左方dp[i][j-1]、上方dp[i-1][j]和左上方dp[i-1][j-1]的值因此我們通常使用兩層循環(huán)i從 1 到mj從 1 到n依次填充即可。最終答案在填充完整個(gè)表格后dp[m][n]就是序列seqS和seqT的最長公共子序列的長度也就是題目所求的“最長公共藍(lán)肽子序列”包含的藍(lán)肽個(gè)數(shù)。4. 完整實(shí)現(xiàn)與代碼詳解理論清晰后我們來看代碼實(shí)現(xiàn)。這里以 C 為例其他語言邏輯相通。4.1 第一步藍(lán)肽分割函數(shù)這是將題目輸入轉(zhuǎn)化為算法輸入的關(guān)鍵一步。vectorstring splitToPeptides(const string s) { vectorstring peptides; string current; for (char c : s) { if (isupper(c)) { // 遇到大寫字母開始新的藍(lán)肽 if (!current.empty()) { peptides.push_back(current); } current c; // 新藍(lán)肽以當(dāng)前大寫字母開始 } else { // 小寫字母追加到當(dāng)前藍(lán)肽 current c; } } // 不要忘記最后一個(gè)藍(lán)肽 if (!current.empty()) { peptides.push_back(current); } return peptides; }實(shí)操心得isupper(c)是 C 標(biāo)準(zhǔn)庫函數(shù)在cctype頭文件中。確保你的代碼包含了這個(gè)頭文件。在 Java 中可以使用Character.isUpperCase(c)在 Python 中可以使用c.isupper()。這個(gè)函數(shù)的健壯性直接決定了后續(xù) DP 的正確性務(wù)必用樣例充分測試。4.2 第二步動(dòng)態(tài)規(guī)劃求解 LCS獲得peptidesS和peptidesT后我們進(jìn)行 DP。int longestCommonPeptideSubsequence(const vectorstring s, const vectorstring t) { int m s.size(); int n t.size(); // 創(chuàng)建 DP 表多一行一列用于邊界條件 vectorvectorint dp(m 1, vectorint(n 1, 0)); // 填充 DP 表 for (int i 1; i m; i) { for (int j 1; j n; j) { if (s[i - 1] t[j - 1]) { // 藍(lán)肽相等 dp[i][j] dp[i - 1][j - 1] 1; } else { // 藍(lán)肽不等 dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }4.3 第三步主函數(shù)與流程整合將上述兩部分組合并處理輸入輸出。#include iostream #include vector #include string #include cctype #include algorithm using namespace std; // 此處插入 splitToPeptides 和 longestCommonPeptideSubsequence 函數(shù) int main() { string s1, s2; cin s1 s2; // 讀取兩個(gè)字符串 vectorstring p1 splitToPeptides(s1); vectorstring p2 splitToPeptides(s2); int ans longestCommonPeptideSubsequence(p1, p2); cout ans endl; return 0; }復(fù)雜度分析時(shí)間復(fù)雜度分割字符串的時(shí)間復(fù)雜度為 O(L1 L2)其中 L 為字符串長度。DP 部分的時(shí)間復(fù)雜度為 O(m * n)其中 m 和 n 分別為兩個(gè)藍(lán)肽序列的長度。在藍(lán)橋杯的約束下字符串長度通常不超過 1000這個(gè)復(fù)雜度是完全可接受的?？臻g復(fù)雜度DP 表占用 O(m * n) 的空間?？梢允褂脻L動(dòng)數(shù)組優(yōu)化到 O(min(m, n))因?yàn)閐p[i][j]只依賴于上一行和當(dāng)前行。但對于本題的數(shù)據(jù)規(guī)模不優(yōu)化也完全可行代碼更清晰。5. 深入分析與常見變式探討解決了基礎(chǔ)問題我們不妨再深入一層看看這個(gè)題目可能如何變化以及我們?nèi)绾闻e一反三。5.1 如果要求輸出具體的藍(lán)肽子序列而不僅僅是長度這是一個(gè)經(jīng)典的 LCS 輸出問題。DP 表dp[i][j]記錄了長度我們可以通過反向回溯來構(gòu)造出其中一個(gè)最長公共子序列?；厮莘椒◤膁p[m][n]開始比較seqS[i-1]和seqT[j-1]如果相等說明這個(gè)藍(lán)肽屬于 LCS將其加入結(jié)果逆序然后i--, j--跳轉(zhuǎn)到dp[i-1][j-1]。如果不相等則比較dp[i-1][j]和dp[i][j-1]如果dp[i-1][j]更大說明 LCS 可能來自上方則i--。否則說明 LCS 可能來自左方則j--。 重復(fù)此過程直到i或j為 0最后將結(jié)果反轉(zhuǎn)即可。vectorstring getLCS(const vectorstring s, const vectorstring t, const vectorvectorint dp) { vectorstring lcs; int i s.size(), j t.size(); while (i 0 j 0) { if (s[i - 1] t[j - 1]) { lcs.push_back(s[i - 1]); // 逆序添加 i--; j--; } else if (dp[i - 1][j] dp[i][j - 1]) { i--; } else { j--; } } reverse(lcs.begin(), lcs.end()); // 反轉(zhuǎn)得到正序 return lcs; }5.2 空間優(yōu)化滾動(dòng)數(shù)組當(dāng)序列長度很大時(shí)比如上萬O(m*n) 的二維數(shù)組可能超出內(nèi)存限制。此時(shí)可以使用滾動(dòng)數(shù)組優(yōu)化。因?yàn)閐p[i][j]只依賴于上一行 (i-1) 和當(dāng)前行我們只需要兩行數(shù)組。int longestCommonPeptideSubsequence_optimized(const vectorstring s, const vectorstring t) { int m s.size(); int n t.size(); vectorvectorint dp(2, vectorint(n 1, 0)); // 只有兩行 int now 0, prev 1; // 當(dāng)前行和上一行的索引 for (int i 1; i m; i) { swap(now, prev); // 滾動(dòng)上一行變成舊的當(dāng)前行新的當(dāng)前行準(zhǔn)備被計(jì)算 for (int j 1; j n; j) { if (s[i - 1] t[j - 1]) { dp[now][j] dp[prev][j - 1] 1; // 注意這里是 prev } else { dp[now][j] max(dp[prev][j], dp[now][j - 1]); } } } return dp[now][n]; }注意事項(xiàng)使用滾動(dòng)數(shù)組時(shí)下標(biāo)對應(yīng)關(guān)系容易出錯(cuò)。dp[now][j]對應(yīng)的是dp[i][j]dp[prev][j]對應(yīng)dp[i-1][j]dp[now][j-1]對應(yīng)dp[i][j-1]而dp[prev][j-1]對應(yīng)dp[i-1][j-1]。務(wù)必理清這個(gè)映射。5.3 與其他子序列問題的關(guān)聯(lián)“藍(lán)肽子序列”本質(zhì)是 LCS而 LCS 是動(dòng)態(tài)規(guī)劃中最為經(jīng)典的模型之一。它與以下問題密切相關(guān)最長遞增子序列 (LIS)LIS 通常有 O(n2) 的 DP 解和 O(n log n) 的貪心二分解。LCS 可以轉(zhuǎn)化為 LIS 問題當(dāng)序列元素為不重復(fù)整數(shù)時(shí)通過映射但通用性不如 DP。編輯距離編輯距離的 DP 狀態(tài)定義與 LCS 神似但轉(zhuǎn)移方程更復(fù)雜包含了插入、刪除、替換操作。最大公共子串子串要求連續(xù)其 DP 定義dp[i][j]通常表示以s[i-1]和t[j-1]結(jié)尾的公共子串長度轉(zhuǎn)移方程也不同。理解它們之間的區(qū)別與聯(lián)系能幫助你構(gòu)建起解決字符串/序列問題的 DP 知識網(wǎng)絡(luò)。6. 實(shí)戰(zhàn)調(diào)試與常見“坑點(diǎn)”即使思路正確代碼實(shí)現(xiàn)時(shí)也可能遇到各種問題。下面是我在多次練習(xí)和教學(xué)中總結(jié)的常見“坑點(diǎn)”。6.1 分割函數(shù)邏輯錯(cuò)誤問題分割結(jié)果不對比如“ABc”被錯(cuò)誤地分割為[“A”, “Bc”]而不是[“ABc”]。排查檢查分割邏輯。關(guān)鍵在于“遇到大寫字母時(shí)是否正確地結(jié)束了上一個(gè)藍(lán)肽”。上面的示例代碼邏輯是遇到大寫字母如果當(dāng)前current非空則保存它。對于“ABc”遍歷到 ‘A‘current為空所以只設(shè)置current“A”遍歷到 ‘B‘它是大寫此時(shí)current“A”非空所以先將“A”保存然后current“B”遍歷到 ‘c‘小寫追加得到current“Bc”循環(huán)結(jié)束保存“Bc”。結(jié)果是[“A”, “Bc”]錯(cuò)誤。修正正確的邏輯應(yīng)該是遇到大寫字母就立即保存當(dāng)前已構(gòu)建的藍(lán)肽無論是否為空然后開始構(gòu)建新的藍(lán)肽。但通常我們初始化current為空遇到大寫字母時(shí)如果current不為空說明我們已經(jīng)構(gòu)建了一個(gè)完整的藍(lán)肽以之前的大寫字母開頭然后我們重置current為當(dāng)前這個(gè)新的大寫字母。對于“ABc”current初始為空。遇到 ‘A‘current為空所以直接current“A”。遇到 ‘B‘current非空為“A”保存“A”然后current“B”。遇到 ‘c‘追加得到“Bc”。結(jié)束保存“Bc”。結(jié)果還是[“A”, “Bc”]。 等等這似乎還是不對題目定義藍(lán)肽是“一個(gè)大寫字母零個(gè)或多個(gè)小寫字母”。“ABc”這個(gè)字符串按照規(guī)則’A‘ 是大寫后面跟著 ‘B‘大寫這不符合“大寫字母后跟小寫字母”的規(guī)則。實(shí)際上“ABc”應(yīng)該被理解為兩個(gè)藍(lán)肽“A”和“Bc”。因?yàn)?‘B‘ 是一個(gè)新的大寫字母它標(biāo)志著一個(gè)新藍(lán)肽的開始。所以[“A”, “Bc”]是正確的分割我之前的假設(shè)錯(cuò)了。“LanQiao”被分為[“Lan”, “Qiao”]也是因?yàn)?‘Q‘ 是大寫字母。結(jié)論原分割函數(shù)邏輯是正確的。關(guān)鍵是要理解題目輸入保證是合法的藍(lán)肽序列連接即一個(gè)大寫字母后可以跟多個(gè)小寫字母直到下一個(gè)大寫字母出現(xiàn)。所以“ABc”就是兩個(gè)藍(lán)肽。6.2 DP數(shù)組下標(biāo)與序列索引對應(yīng)錯(cuò)誤問題在 DP 循環(huán)中訪問seqS[i]和seqT[j]時(shí)發(fā)生越界或者邏輯錯(cuò)誤。排查牢記我們的定義dp[i][j]對應(yīng)seqS的前i個(gè)和seqT的前j個(gè)。因此在循環(huán)中i從 1 到mj從 1 到n而比較的藍(lán)肽應(yīng)該是seqS[i-1]和seqT[j-1]。這是最容易出錯(cuò)的地方之一。修正統(tǒng)一使用i和j作為 DP 表下標(biāo)使用i-1和j-1作為序列索引。在代碼中寫清楚注釋。6.3 輸入讀取與邊界條件問題題目可能包含空格藍(lán)橋杯的字符串輸入通常使用cin s這會(huì)讀到空白字符為止。如果字符串本身沒有空格這沒問題。但為了穩(wěn)健可以使用getline(cin, s)讀取整行。但要注意如果之前有cin讀取其他整數(shù)可能會(huì)留下?lián)Q行符需要cin.ignore()來清除。排查仔細(xì)閱讀題目輸入格式。本題通常就是兩個(gè)字符串中間用空格或換行隔開。用cin s1 s2是安全的。邊界條件空字符串。分割函數(shù)應(yīng)能正確處理空字符串返回空向量。DP 部分dp[0][j]和dp[i][0]初始化為 0也能正確處理。6.4 內(nèi)存與性能問題在本地測試通過但提交后出現(xiàn)“內(nèi)存超限”或“時(shí)間超限”。排查內(nèi)存檢查 DP 數(shù)組大小。如果字符串長度最大為 1000最壞情況下每個(gè)字符都是大寫字母藍(lán)肽序列長度也可能達(dá)到 1000。dp[1001][1001]的int數(shù)組大約占 4MB在 128MB/256MB 的限制下是安全的。但如果開到dp[10000][10000]就危險(xiǎn)了。時(shí)間O(m*n) 的復(fù)雜度對于 m, n 1000計(jì)算量在 10^6 級別C 完全可以在 1秒內(nèi)完成。如果超時(shí)可能是寫了三重循環(huán)或其他低效操作。修正確保 DP 是嚴(yán)格的兩層循環(huán)。如果數(shù)據(jù)規(guī)模真的很大比如 10^4就必須使用滾動(dòng)數(shù)組優(yōu)化空間但時(shí)間復(fù)雜度 O(m*n) 可能依然堪憂需要考慮更優(yōu)的算法如對于特定情況轉(zhuǎn)化為 LIS 用 O(n log n) 求解但本題不需要。7. 從“解題”到“掌握”如何高效備戰(zhàn)此類題型一道好的競賽題其價(jià)值不止于 AC。對于“藍(lán)肽子序列”這類題目我建議通過以下步驟進(jìn)行深度學(xué)習(xí)以達(dá)到舉一反三的效果。第一步嚴(yán)格實(shí)現(xiàn)與測試不要滿足于通過樣例。自己構(gòu)造邊界數(shù)據(jù)空字符串與空字符串。一個(gè)空字符串和一個(gè)非空字符串。兩個(gè)完全相同的字符串。兩個(gè)完全不同的字符串如全大寫字母序列。隨機(jī)生成的長字符串用你的程序和另一種思路如暴力搜索小數(shù)據(jù)對比結(jié)果。第二步嘗試不同解法與輸出在確?；A(chǔ) DP 解法正確后可以挑戰(zhàn)自己實(shí)現(xiàn)輸出具體序列的版本。實(shí)現(xiàn)滾動(dòng)數(shù)組優(yōu)化的版本。思考如果題目要求的是“最短公共超序列”Shortest Common Supersequence的長度該如何修改事實(shí)上SCS 長度 len(s) len(t) - LCS 長度。第三步歸類與總結(jié)將這道題放入你的知識體系標(biāo)簽動(dòng)態(tài)規(guī)劃、線性 DP、最長公共子序列 (LCS)、字符串處理。解題模板寫出清晰的 DP 狀態(tài)定義和轉(zhuǎn)移方程。對于 LCS 問題這個(gè)模板幾乎通用。抽象模式識別題目如何將“藍(lán)肽”這個(gè)外衣套在 LCS 模型上。很多題目都是這樣核心是經(jīng)典模型但增加了預(yù)處理步驟如本題的分割或改變了比較單位從字符到字符串。第四步橫向拓展練習(xí)找一些同類題目進(jìn)行鞏固例如LeetCode 1143. 最長公共子序列裸題LeetCode 1035. 不相交的線本質(zhì)是 LCSLeetCode 1092. 最短公共超序列進(jìn)階藍(lán)橋杯真題中其他涉及 DP 和字符串的題目如編輯距離、最大子串和等。通過這樣的閉環(huán)學(xué)習(xí)下次再遇到“XX子序列”問題你就能迅速看穿本質(zhì)調(diào)用正確的“武器庫”來解決問題。競賽編程說到底是在比拼快速且準(zhǔn)確地將實(shí)際問題映射到已知數(shù)學(xué)模型的能力?！八{(lán)肽子序列”正是訓(xùn)練這種能力的絕佳范例。