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