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