1. 問題引入從一個看似簡單的字符串問題說起最近在整理歷年算法競賽的經(jīng)典題目時我又翻到了2020年第十一屆藍(lán)橋杯國賽C B組的這道“本質(zhì)上升序列”。說實話第一次看到這個題目名字很多人的第一反應(yīng)可能和我當(dāng)初一樣這不就是個求上升子序列個數(shù)的問題嗎動態(tài)規(guī)劃DP的經(jīng)典例題用dp[i]表示以第i個字符結(jié)尾的上升子序列個數(shù)然后兩層循環(huán)累加一下不就完了但如果你真的這么想并且動手去寫代碼大概率會在某個測試用例上栽跟頭。這道題的“本質(zhì)”二字恰恰是它最大的陷阱和精髓所在。它考察的遠(yuǎn)不止是基礎(chǔ)的動態(tài)規(guī)劃更是對問題定義的深刻理解、對去重邏輯的嚴(yán)密思考以及對算法效率的極致追求。我記得當(dāng)時賽場上有不少高手都在這里卡了殼不是結(jié)果不對就是程序超時。今天我就結(jié)合自己多次解題和教學(xué)的經(jīng)驗把這道題從里到外、從暴力解法到最優(yōu)解法的完整思考過程拆解給你看。無論你是正在備賽藍(lán)橋杯的選手還是對算法感興趣的開發(fā)者相信這篇深度解析都能讓你對“子序列計數(shù)”這一類問題有全新的認(rèn)識。題目描述通常很簡單給定一個全部由小寫字母組成的字符串s長度可達(dá)200要求計算出其所有“本質(zhì)不同的上升子序列”的個數(shù)并對結(jié)果取模通常是10^9 7。這里的“上升子序列”定義為從原字符串中按順序取出一些字符可以不連續(xù)使得這些字符從左到右是嚴(yán)格字典序遞增的。而“本質(zhì)不同”則意味著即使兩個子序列由原字符串中不同位置的字符組成只要它們最終形成的字符串完全相同也只能算作同一個子序列。舉個例子字符串a(chǎn)bac。子序列a取第一個字符和子序列a取第三個字符是同一個字符串a(chǎn)因此它們屬于同一個“本質(zhì)”的子序列只能計一次數(shù)。而子序列ab和ac則是兩個不同的字符串需要分別計數(shù)。我們的目標(biāo)就是計算所有可能的不同字符串的個數(shù)。2. 從陷阱開始為什么不能直接用經(jīng)典LIS計數(shù)DP我們先來看看最直觀、也最容易出錯的思路——修改經(jīng)典的最長上升子序列LIS計數(shù)DP算法。對于最長上升子序列的計數(shù)我們通常會維護兩個數(shù)組len[i]記錄以s[i]結(jié)尾的最長上升子序列長度cnt[i]記錄以s[i]結(jié)尾的、長度為len[i]的上升子序列的個數(shù)。然后通過雙層循環(huán)進行轉(zhuǎn)移。但是請注意LIS計數(shù)DP求的是“最長長度”的序列個數(shù)并且通常不去重即不同位置構(gòu)成的相同序列算不同方案。而本題要求的是所有長度的上升子序列不僅僅是最長的。本質(zhì)不同即最終形成的字符串相同就算同一個。如果我們試圖用dp[i]直接表示以s[i]結(jié)尾的、所有上升子序列的個數(shù)不去重然后最后對所有的dp[i]求和會立刻遇到兩個問題問題A如何保證“上升”嚴(yán)格遞增這相對好解決在轉(zhuǎn)移時只有當(dāng)s[j] s[i]j i時才能把以s[j]結(jié)尾的序列后面接上s[i]。問題B如何避免重復(fù)計數(shù)這是核心難點。假設(shè)字符串是aba計算dp[2]以最后一個a結(jié)尾。當(dāng)j0時s[0]as[2]a不滿足s[j] s[i]所以不能轉(zhuǎn)移。這看起來沒問題。但考慮子序列a它既可以是s[0]也可以是s[2]。在我們的定義下dp[0]和dp[2]都包含了只包含一個a的情況即序列本身。如果我們最后簡單地將所有dp[i]相加那么子序列a就會被計算兩次。你可能會想那我初始化的時候dp[i]只包含長度為1的序列即字符本身然后轉(zhuǎn)移時只從前面更小的字符累加過來不就能避免同一個字符結(jié)尾的重復(fù)了嗎但問題沒那么簡單?？紤]abac我們關(guān)注以最后一個c結(jié)尾的序列。ac這個序列可以由s[0](a)和s[3](c)組成也可以由s[2](a)和s[3](c)組成。如果我們用dp[3] dp[0] dp[2]那么ac這個字符串就會被計算兩次因為dp[0]和dp[2]都包含了a這個前綴。然而dp[0]和dp[2]所代表的a在“本質(zhì)”上是同一個字符串。因此在向c轉(zhuǎn)移時a這個前綴不應(yīng)該被重復(fù)累加。所以癥結(jié)在于以不同位置i結(jié)尾的dp[i]值可能包含了相同的子序列字符串。直接對dp[i]求和必然導(dǎo)致重復(fù)。3. 思維轉(zhuǎn)換按“結(jié)尾字符”和“序列字符串”來規(guī)劃既然按“以位置i結(jié)尾”來定義狀態(tài)會導(dǎo)致重復(fù)我們必須換一個角度。題目要求的是不同的“字符串”個數(shù)那么我們的狀態(tài)能不能直接和“字符串”掛鉤呢一個關(guān)鍵的洞察是對于一個確定的結(jié)尾字符ch比如c所有以ch結(jié)尾的本質(zhì)不同的上升子序列其前一個字符一定是一個比ch小的字符比如a或b并且這些前綴本身也是互不相同的上升子序列。這引導(dǎo)我們定義一個新的狀態(tài)f[ch]表示以字符ch結(jié)尾的、所有本質(zhì)不同的上升子序列的個數(shù)。這里ch是a到z的26個小寫字母之一。那么如何計算f[ch]呢假設(shè)我們正在遍歷原字符串s當(dāng)前遍歷到字符s[i] ch。所有以ch結(jié)尾的新序列都可以由“某個以比ch小的字符結(jié)尾的舊序列”后面加上ch得到再加上ch本身作為一個單獨的序列。因此一個初步的轉(zhuǎn)移方程浮出水面f[ch] sum(f[pre_ch]) 1其中pre_ch遍歷所有比ch小的字符sum(f[pre_ch])表示所有可能的、以更小字符結(jié)尾的序列后面添加ch所產(chǎn)生的新序列1表示序列ch本身。但是這里依然隱藏著一個巨大的陷阱也是本題最精妙的地方。讓我們用字符串a(chǎn)bac來手動模擬一下假設(shè)我們從左到右遍歷讀到s[0] a比a小的字符不存在所以f[a] 0 1 1。這表示目前有一個以a結(jié)尾的序列a。讀到s[1] b比b小的字符有af[a]1。所以f[b] f[a] 1 1 1 2。這兩個序列是b和ab。讀到s[2] a注意又讀到了一個a。按照公式比a小的字符不存在所以f[a] 0 1 1不對如果這樣我們就把之前第一個a產(chǎn)生的序列a給覆蓋掉了。但實際上新來的這個a它本身作為一個序列a和之前第一個a形成的序列a是“本質(zhì)相同”的不應(yīng)該重復(fù)創(chuàng)建。然而這個新的a可以作為后續(xù)序列的結(jié)尾。更重要的是它會影響后續(xù)字符的轉(zhuǎn)移嗎仔細(xì)思考對于后續(xù)的字符比如后面的c它可以從前面任意一個a后面接上。但是如果前面有兩個a它們提供的、以a結(jié)尾的序列集合是完全一樣的目前都只有a這一個序列。那么當(dāng)c計算f[c]時如果簡單累加f[a]就會因為f[a]被錯誤地累加兩次實際上兩個a對應(yīng)的是同一個集合而導(dǎo)致重復(fù)。所以當(dāng)我們遇到一個重復(fù)的字符時關(guān)鍵點在于不能簡單地用1去初始化或更新f[ch]而是要避免對同一“結(jié)尾狀態(tài)”的重復(fù)貢獻。4. 正解剖析動態(tài)規(guī)劃與容斥原理的結(jié)合正確的解法需要結(jié)合動態(tài)規(guī)劃和一種類似“容斥”的思想。我們定義dp[i]表示以字符串中第i個位置的字符作為結(jié)尾所能形成的所有本質(zhì)不同的上升子序列的個數(shù)。last[ch]一個輔助數(shù)組記錄字符ch上一次出現(xiàn)的位置索引。初始化為-1。核心思想是當(dāng)我們遍歷到第i個字符s[i] ch時所有以ch結(jié)尾的新序列可以由所有在i之前、且字符小于ch的位置j的dp[j]值轉(zhuǎn)移過來。但是如果ch這個字符之前出現(xiàn)過即last[ch] ! -1那么我們需要減去上一次出現(xiàn)時從同樣的那些更小字符轉(zhuǎn)移過來的部分因為那部分序列在上一次已經(jīng)貢獻給了以ch結(jié)尾的序列集合本次再累加就會導(dǎo)致重復(fù)。讓我們形式化地描述這個過程并配合abac的例子進行演算初始化dp數(shù)組全為0last數(shù)組全為-1?？偞鸢竌ns 0。遍歷字符串s的每個位置i(從0開始) a. 當(dāng)前字符ch s[i]。 b. 我們計算dp[i]的初始值為1代表序列ch本身。 c. 然后我們遍歷所有比ch小的字符pre_ch從a到ch-1 * 我們需要知道到目前為止所有以pre_ch結(jié)尾的本質(zhì)不同序列有多少種。注意這不是簡單地找最后一個pre_ch的位置因為以pre_ch結(jié)尾的序列可能分散在多個位置。實際上所有出現(xiàn)過pre_ch的位置j的dp[j]值之和就是以pre_ch結(jié)尾的所有本質(zhì)不同序列的總數(shù)。我們可以維護一個前綴和數(shù)組sum[pre_ch]來動態(tài)記錄這個值。 * 因此dp[i] sum[pre_ch]。這意味著我們可以把每一個以pre_ch結(jié)尾的序列后面都添上ch形成一個新的以ch結(jié)尾的序列。 d. 現(xiàn)在關(guān)鍵步驟來了如果last[ch] ! -1說明當(dāng)前字符ch不是第一次出現(xiàn)。在上一次ch出現(xiàn)的位置記為p last[ch]我們在計算dp[p]時也已經(jīng)加上了當(dāng)時的所有sum[pre_ch]。那么對于本次計算出的dp[i]其中由sum[pre_ch]轉(zhuǎn)移而來的這部分序列可能在上一次就已經(jīng)被創(chuàng)建過了如果前綴序列集合沒有變化。為了去重我們需要dp[i] - dp[p]等一下這里需要仔細(xì)推敲。 更準(zhǔn)確地說上一次ch出現(xiàn)時dp[p]已經(jīng)包含了“從當(dāng)時的所有更小字符結(jié)尾的序列轉(zhuǎn)移過來”的部分。而這一次sum[pre_ch]可能比上一次更大因為中間可能插入了新的以pre_ch結(jié)尾的序列。本次新增的、可能產(chǎn)生重復(fù)的轉(zhuǎn)移量恰好等于上一次ch出現(xiàn)時它所接收到的轉(zhuǎn)移量也就是dp[p] - 1因為要減去ch本身這個序列。為什么因為本次計算dp[i]時我們加上的sum[pre_ch]是當(dāng)前的總和。而上一次dp[p]計算時加上的sum[pre_ch]是當(dāng)時的總和。兩者的差值(sum[pre_ch] - sum[pre_ch])是這期間新增的以pre_ch結(jié)尾的序列這部分是全新的不會重復(fù)。而sum[pre_ch]這部分在上一次已經(jīng)被用來生成過以ch結(jié)尾的序列了所以本次如果再直接用sum[pre_ch]加就會把sum[pre_ch]這部分重復(fù)加一次。而sum[pre_ch]就等于dp[p] - 1。 因此正確的去重操作是dp[i] - (dp[p] - 1)不更簡潔且正確的寫法是dp[i] - dp[p]但需要在更新sum數(shù)組之前記錄舊的dp[p]值然后本次的dp[i]實際上等于1 sum[pre_ch] - old_dp[p]其中old_dp[p]是dp[p]在本次更新前的值。在實際編碼中有一個更清晰的做法 * 先計算一個臨時值temp 1。 * 對于每個比ch小的pre_chtemp sum[pre_ch]。 * 如果last[ch] ! -1則temp - dp[last[ch]]。注意這里減去的dp[last[ch]]是上一次出現(xiàn)時計算出的、以那個位置的ch結(jié)尾的所有序列數(shù)。這個值恰好包含了上一次從所有更小字符轉(zhuǎn)移過來的總量即當(dāng)時的sum[pre_ch]。 * 然后dp[i] temp。 e. 更新sum[ch] dp[i]。這表示以字符ch結(jié)尾的序列總數(shù)增加了dp[i]。 f. 更新last[ch] i。 g. 可選將dp[i]累加到總答案ans中。注意dp[i]表示以第i個位置結(jié)尾的序列數(shù)這些序列彼此本質(zhì)不同并且與以其他位置結(jié)尾的序列也可能本質(zhì)相同但我們在計算dp[i]時通過減法已經(jīng)避免了這種重復(fù)。最終所有dp[i]的和就是答案。更高效的是在更新sum[ch]后總答案其實就是所有sum[ch]ch從a到z的總和。讓我們用abac走一遍這個流程is[i]計算過程 (temp初值1)last[s[i]]舊值減法操作dp[i]最終值更新 sum[s[i]]更新 last[s[i]]累計答案ans (或總sum)0atemp1。比a小的字符無。last[a]-1不減。-1無dp[0]1sum[a]011last[a]0ans11btemp1。比b小的字符有asum[a]1temp112。last[b]-1不減。-1無dp[1]2sum[b]022last[b]1ans1232atemp1。比a小的字符無。last[a]0需要減去 dp[last[a]]即dp[0]1。temp1-10。0temp - dp[0] (1)dp[2]0sum[a]101last[a]2ans3033ctemp1。比c小的字符有a,b。sum[a]1sum[b]2temp1124。last[c]-1不減。-1無dp[3]4sum[c]044last[c]3ans347最終答案 ans 7。讓我們驗證一下字符串a(chǎn)bac的所有本質(zhì)上升子序列長度為1:a,b,c- 3個長度為2:ab,ac,bc- 3個 (注意aa不上升)長度為3:abc- 1個長度為4: 無 總共 331 7個。符合計算結(jié)果。注意a只被計算了一次盡管它出現(xiàn)在兩個位置。5. 算法實現(xiàn)與細(xì)節(jié)打磨理解了原理代碼實現(xiàn)就相對清晰了。我們需要維護以下幾個數(shù)據(jù)結(jié)構(gòu)dp[i]以第i個字符結(jié)尾的本質(zhì)不同上升子序列個數(shù)。由于我們只需要用到最新的dp[i]來更新sum和last有時可以只用一個臨時變量cur。sum[26]sum[ch]表示以字符ch結(jié)尾的所有本質(zhì)不同上升子序列的總數(shù)。這是動態(tài)更新的前綴和。last[26]last[ch]記錄字符ch最近一次出現(xiàn)的位置索引。初始化為 -1。最終答案所有sum[ch]的總和。這里給出一個典型的C實現(xiàn)并附上詳細(xì)注釋#include iostream #include string #include vector using namespace std; const int MOD 1e9 7; // 按題目要求取模 int main() { string s; cin s; int n s.length(); vectorlong long dp(n, 0); // dp[i] vectorlong long sum(26, 0); // sum[ch] vectorint last(26, -1); // last[ch] long long total 0; // 總答案也可以最后累加sum for (int i 0; i n; i) { int ch s[i] - a; long long cur 1; // 序列 s[i] 本身 // 累加所有比當(dāng)前字符小的字符的 sum for (int pre 0; pre ch; pre) { cur (cur sum[pre]) % MOD; } // 去重如果當(dāng)前字符之前出現(xiàn)過減去上一次以該字符結(jié)尾的序列總數(shù) if (last[ch] ! -1) { // 注意這里減法要加MOD再取模防止出現(xiàn)負(fù)數(shù) cur (cur - dp[last[ch]] MOD) % MOD; } dp[i] cur; // 記錄當(dāng)前dp值 sum[ch] (sum[ch] cur) % MOD; // 更新以ch結(jié)尾的總數(shù) last[ch] i; // 更新字符ch最后出現(xiàn)的位置 total (total cur) % MOD; // 累加到總答案 } cout total endl; return 0; }幾個至關(guān)重要的細(xì)節(jié)和避坑點減法取模cur (cur - dp[last[ch]] MOD) % MOD;這行代碼是安全的保證。在模運算中直接做減法可能得到負(fù)數(shù)加上一個模數(shù)MOD再取?？梢源_保結(jié)果在[0, MOD-1]范圍內(nèi)。數(shù)據(jù)類型使用long long。因為序列個數(shù)可能非常多在取模前可能會超過int的范圍。初始化與遍歷順序sum數(shù)組初始為0last數(shù)組初始為-1。遍歷字符串的順序是自然的從左到右這保證了當(dāng)我們計算cur時sum[pre]已經(jīng)包含了所有在當(dāng)前位置i之前出現(xiàn)的、以pre字符結(jié)尾的序列信息。為什么是- dp[last[ch]]這是理解去重的核心。dp[last[ch]]包含了上一次出現(xiàn)字符ch時從所有更小字符pre轉(zhuǎn)移過來的序列數(shù)即當(dāng)時的sum[pre]之和。本次計算cur時我們又加上了當(dāng)前的sum[pre]。當(dāng)前的sum[pre]等于舊的sum[pre] 期間新增的序列。減去dp[last[ch]]就恰好減去了“舊的sum[pre]”這部分重復(fù)累加的量。復(fù)雜度分析時間復(fù)雜度為 O(26 * n)因為對于每個字符我們需要遍歷26個字母中的一部分最多25個來累加sum。對于長度 n200 是綽綽有余的?？臻g復(fù)雜度 O(n26)。6. 舉一反三變種問題與思維延伸解決了這道題我們不妨思考幾個相關(guān)的變種問題這能幫助你鞏固這種“狀態(tài)定義”和“去重”的思想如果不要求“本質(zhì)不同”只求所有上升子序列的個數(shù)不同位置算不同這就簡單多了。定義dp[i]為以第i個位置結(jié)尾的上升子序列個數(shù)允許重復(fù)。轉(zhuǎn)移方程為dp[i] 1 sum(dp[j])其中j i且s[j] s[i]。最后答案就是所有dp[i]的和。不需要last數(shù)組和去重操作。如果求的是“本質(zhì)不同的非下降子序列”即允許相等字符個數(shù)此時“上升”條件變?yōu)閟[j] s[i]。去重邏輯需要調(diào)整嗎需要而且更復(fù)雜。因為當(dāng)s[i] s[j] (j i)時以s[i]結(jié)尾的新序列不僅會與之前s[j]結(jié)尾的序列重復(fù)還可能因為中間插入的相同字符產(chǎn)生新的重復(fù)組合。通常的解法是在遍歷時對于字符ch我們不僅要從更小的字符轉(zhuǎn)移還要從相同的字符轉(zhuǎn)移但同時要減去最近一次相同字符出現(xiàn)時所累積的、從更小字符轉(zhuǎn)移過來的“增量”部分以避免重復(fù)。這需要更精巧地維護狀態(tài)。如果字符串長度非常大例如10^5字符集也很大比如整個ASCII可打印字符我們內(nèi)層循環(huán)for (int pre 0; pre ch; pre)的復(fù)雜度 O(字符集大小) 可能成為瓶頸。此時可以用樹狀數(shù)組Fenwick Tree或線段樹來維護sum數(shù)組的前綴和。這樣求“所有比ch小的字符的sum之和”這個操作可以從 O(K) 優(yōu)化到 O(log K)其中 K 是字符集大小。通過這道“本質(zhì)上升序列”我們深刻體會到在動態(tài)規(guī)劃中狀態(tài)的定義直接決定了問題的復(fù)雜度和正確性。當(dāng)經(jīng)典思路遇到障礙時不妨退一步重新審視問題的本質(zhì)約束本題是“本質(zhì)不同”并嘗試將狀態(tài)與這個約束更直接地關(guān)聯(lián)起來本題從“以位置結(jié)尾”轉(zhuǎn)向“以字符結(jié)尾”并輔以前綴和與去重。這種思維訓(xùn)練對于解決競賽中更復(fù)雜的計數(shù)問題至關(guān)重要。