1. 項目概述一道經典的動態規劃計數題最近在整理藍橋杯的歷年真題特別是國賽B組的題目發現“本質上升序列”這道題試題 D的出鏡率相當高也經常被拿出來作為動態規劃DP和字符串處理的經典例題來討論。很多剛接觸算法競賽的同學一看到“上升序列”、“不同子序列”這些詞就容易發懵感覺概念纏繞在一起理不清頭緒。這道題恰恰是一個很好的切入點它不像一些復雜的圖論或數論題那樣需要深厚的數學背景而是更考驗我們對問題本質的抽象能力和對DP狀態定義的精準把握。簡單來說題目會給你一個字符串比如lanqiao要求你找出這個字符串中所有的“本質不同的上升子序列”的個數。這里有兩個關鍵約束“本質不同”和“上升”。“上升”在字符串的語境下通常指的是子序列中字符的索引是嚴格遞增的這是子序列的天然定義一般無需特別處理。而“本質不同”則意味著即使兩個子序列由相同的字符組成只要它們在原字符串中的位置索引不同就被視為不同的序列。這才是題目的核心難點和考點它要求我們計數時必須基于字符在原串中的位置來區分而不能僅僅看字符本身。舉個例子字符串aab。如果只考慮由字符組成的子序列a出現了兩次但這兩個a來自原串中不同位置索引0和索引1因此它們是兩個不同的“本質上升序列”。同樣ab也有兩個一個由索引0的a和索引2的b組成另一個由索引1的a和索引2的b組成。所以總數為 2單個a 2ab 1單個b 5。如果錯誤地按字符集去重就會得到錯誤結果。解決這類問題暴力枚舉所有子序列顯然不可行時間復雜度 O(2^n)。標準的解法是使用動態規劃。但具體怎么定義狀態怎么轉移怎么保證計數不重不漏里面有不少細節和技巧。接下來我就結合自己的解題和教學經驗把這道題從思路到代碼再到各種變體和坑點徹底拆解清楚。2. 核心思路解析與動態規劃狀態設計面對“本質不同的上升子序列計數”問題我們首先要摒棄“先找出所有子序列再去重”的暴力想法。動態規劃的精髓在于利用已計算的信息高效地遞推出新的信息。我們的目標是設計一個DP狀態使得在遞推過程中天然地滿足“本質不同”和“上升”的要求。2.1 為什么是動態規劃字符串子序列計數問題尤其是要求“不同”的計數非常適合用DP解決。因為子序列的生成具有明顯的階段性按原串順序逐個考慮字符并且后一個字符能否接在前面的序列之后只取決于前面序列的最后一個字符或者更廣義地說最后一個字符的位置和大小。這滿足了DP的“無后效性”條件。2.2 狀態定義的藝術最直接的想法是定義dp[i]表示“以第i個字符結尾的本質不同的上升子序列”的個數。這個定義很直觀但存在一個重大問題當我們在后續位置j (j i)考慮字符s[j]時如果s[j] s[i]那么s[j]可以接在所有以s[i]結尾的子序列后面形成新的子序列。但是不同的i可能對應相同的字符s[i]。例如aab有兩個a。以第一個a結尾的序列有{a}以第二個a結尾的序列也有{a}。如果我們簡單地將dp[j]加上所有滿足s[i] s[j]的dp[i]那么對于s[j] b它會同時加上dp[0]和dp[1]都是1從而認為可以形成兩個ab。這看起來是對的但這里隱藏了重復計數的問題嗎讓我們深入思考“本質不同”。序列ab有兩個分別是(索引0, 索引2)和(索引1, 索引2)。在我們的計算中dp[2]對應字符b 應該最終等于2代表以b結尾的序列有兩個ab來自第一個a和ab來自第二個a。但是dp[i]本身表示“以 i 結尾”的序列數這個定義已經隱含了位置信息。所以只要我們在轉移時讓dp[j]累加所有i j 且 s[i] s[j]的dp[i]那么來自不同i的貢獻自然就是不同的序列因為它們結尾的a的位置不同。然而還有一個更棘手的問題單個字符構成的子序列。按照dp[i]的定義它包含了以i結尾的所有序列這自然也包括長度為1的序列即字符s[i]本身。那么dp[i]的初始值應該是什么如果設為1代表序列{s[i]}本身那么在轉移時dp[j]累加dp[i]時就會把{s[i]}這個序列后面加上s[j]形成{s[i], s[j]}這是正確的。但是最終的總數如果簡單地將所有dp[i]相加會不會重復計算不會因為每個dp[i]計數的是以特定位置i結尾的序列它們彼此互斥。所以狀態定義dp[i]是可行的。最終答案就是sum(dp[0], dp[1], ..., dp[n-1])其中n是字符串長度。2.3 狀態轉移方程的推導基于狀態dp[i]以字符串中第i個位置索引從0開始的字符結尾的、本質不同的嚴格上升子序列的個數。初始化對于每個位置i至少有一個以其自身結尾的、長度為1的子序列。因此dp[i]的初始值為 1。轉移方程對于當前位置j我們需要考慮所有在它之前的位置i (0 i j)。如果s[i] s[j]注意題目中的“上升”在字符序列中通常指字典序或數值序對于小寫字母就是ASCII碼的大小那么所有以s[i]結尾的上升子序列在其末尾添加上s[j]后仍然是一個上升子序列并且由于結尾變成了j這個新序列自然是以j結尾的。因此轉移方程為dp[j] 1 sum(dp[i])其中i滿足0 i j且s[i] s[j]。這里的1代表長度為1的子序列即s[j]本身。sum(dp[i])代表了所有能以s[j]接在后面形成更長序列的情況。關鍵點為什么這樣能保證“本質不同”因為dp[i]中的每個序列都由其具體的字符索引路徑唯一確定。當s[j]接在某個以i結尾的特定序列后面時產生的新序列的路徑是原路徑加上j這個路徑是唯一的。即使兩個不同的i1和i2對應的字符相同s[i1] s[i2]但由于i1 ! i2它們所代表的“以該位置結尾的序列集合”是不同的因此貢獻給dp[j]的序列也是不同的。2.4 復雜度分析與初步實現根據上述方程我們需要對每個j遍歷所有i j。這是一個典型的雙重循環結構。時間復雜度O(n2)其中 n 是字符串長度。對于藍橋杯的題目字符串長度一般控制在幾百到幾千O(n2) 通常是可接受的。空間復雜度O(n)用于存儲dp數組。一個最基礎的C實現框架如下#include iostream #include string #include vector using namespace std; int countDistinctIncreasingSubseq(string s) { int n s.length(); vectorlong long dp(n, 0); // 使用long long防止大數溢出 long long ans 0; for (int j 0; j n; j) { dp[j] 1; // 初始化自身作為一個序列 for (int i 0; i j; i) { if (s[i] s[j]) { dp[j] dp[i]; } } ans dp[j]; } return ans; // 注意ans可能很大題目可能要求取模 }這就是最核心的解法。但是這道題的魅力和坑點遠不止于此。上面的解法是基礎但在實際競賽中可能會遇到各種變體和需要優化的地方。3. 細節深化、優化與變體分析掌握了基礎DP解法我們才算剛剛入門。在實際應用中尤其是面對藍橋杯這種對效率和正確性要求極高的競賽我們需要考慮更多。3.1 處理大數與取模問題藍橋杯的題目往往不滿足于小規模數據。當字符串長度達到幾千且字符分布較均勻時本質上升序列的數量會呈指數級增長很容易超出int甚至long long的范圍。因此題目經常會要求對結果取模例如1e9 7。注意取模運算必須在加法和乘法過程中隨時進行防止中間結果溢出。同時要特別注意負數取模的問題在C中%運算符對負數取模的結果是負數需要調整。修改后的代碼需加入取模const int MOD 1e9 7; int countDistinctIncreasingSubseq(string s) { int n s.length(); vectorint dp(n, 0); // 改用int因為會取模 int ans 0; for (int j 0; j n; j) { dp[j] 1; // 自身序列 for (int i 0; i j; i) { if (s[i] s[j]) { dp[j] (dp[j] dp[i]) % MOD; } } ans (ans dp[j]) % MOD; } return ans; }3.2 當“上升”定義變化時我們之前的討論基于s[i] s[j]這是最常見的字典序ASCII碼嚴格上升。但如果題目變體呢非嚴格上升不下降即允許s[i] s[j]。這時問題會變得更復雜因為要處理相等字符帶來的重復計數。自定義順序例如規定a z b y這種非常規順序。這時只需將比較條件s[i] s[j]替換為一個自定義的比較函數即可。重點討論非嚴格上升如果允許相等那么當s[i] s[j]時以i結尾的序列后面加上s[j]會形成一個新的以j結尾的序列。但是這里必須非常小心地處理重復例如字符串aa。按照樸素想法dp[0] 1(序列a0)計算dp[1]i0, s[0]a s[1]所以dp[1] 1 dp[0] 2。這表示以第二個a結尾的序列有{a1}和{a0, a1}。總答案 dp[0] dp[1] 3。但實際上序列有哪些{a0},{a1},{a0, a1}。這看起來是對的。但再看aba按上述邏輯計算最終會包含{a0, a2}和{a1, a2}嗎注意s[2]是as[0]和s[1]都是a且s[0] s[2]?不是等于。所以按照s[i] s[j]它們應該被計入。但{a0, a2}和{a1, a2}是本質不同的嗎是的因為中間的字符索引不同。所以算法似乎仍然有效這里有一個巨大的陷阱。考慮aaadp[0] 1dp[1] 1 dp[0] 2(序列a1,a0, a1)dp[2] 1 dp[0] dp[1] 1124(序列a2,a0, a2,a1, a2,a0, a1, a2)總和 1247。但我們手動枚舉所有非嚴格上升子序列a0a1a2a0, a1a0, a2a1, a2a0, a1, a2正好7個。看起來沒錯。但是如果我們改變計算順序或者深究DP的定義會發現這個樸素加法在更復雜的情況下會導致重復計算。問題出在哪里出在當s[i] s[j]時dp[j]直接加上了dp[i]。這意味著所有以i結尾的序列都復制了一份到j的名下并把結尾改為j。這在i和j之間沒有其他相等字符時是可行的。但如果有多個相等的字符就會重復。更嚴謹的做法是對于非嚴格上升我們需要保證對于相同的字符只在最后一次出現時計算所有以其結尾的序列。否則同一個序列會因為可以通過不同位置的相同字符作為“最后一步”而產生多次貢獻。正確的狀態定義需要改變dp[i]表示以第 i 個位置結尾的本質不同的非下降子序列個數但在轉移時對于字符ch我們只應該從上一個字符ch出現的位置轉移過來而不是所有更早的位置。這通常需要維護一個last[ch]數組記錄字符ch上一次出現時的DP值總和。當遇到新的s[j]時dp[j] 1 sum(dp[i] for all i j where s[i] s[j])但需要減去之前相同字符已經計算過的部分。這變得非常復雜。實操心得在競賽中如果遇到“非嚴格上升”的計數一定要先用手動枚舉小例子如”aa“”aab“”aba“”aaa“驗證自己的DP方程是否正確。通常這類問題會轉化為對每個字符維護一個累積和并利用容斥原理來避免重復。一個常見的技巧是定義dp[j]為以s[j]結尾的序列數同時維護一個sum[ch]表示當前以字符ch結尾的所有序列總數。當處理到s[j]時dp[j] 1 sum(sum[ch])其中ch遍歷所有小于等于s[j]的字符。然后更新sum[s[j]] dp[j]注意這里是賦值不是累加因為新的dp[j]已經包含了所有以小于等于s[j]的字符結尾的序列后面接上s[j]的情況而舊的sum[s[j]]對應的那些序列的結尾位置更早它們已經包含在新的dp[j]的生成路徑中了如果累加就會重復。最后答案就是所有sum[ch]的總和。這種方法可以將復雜度優化到 O(n * 字符集大小)。3.3 算法優化從 O(n2) 到 O(n log n) 或 O(n * 26)對于基礎DP的 O(n2) 算法當 n 達到 10^5 時就不行了。我們需要優化內層循環——即快速求出“所有在j之前且字符小于s[j]的dp[i]之和”。這本質上是一個動態前綴和問題。字符集通常是有限的如小寫字母26個。我們可以維護一個數組prefixSum[26]其中prefixSum[k]表示當前所有字符小于等于char(ak)的、且位置在j之前的dp[i]值的總和。那么對于當前位置j的字符c我們需要所有字符嚴格小于c的dp值之和即prefixSum[c - a - 1]如果c是a則為0。然后dp[j] 1 這個和。更新prefixSum數組對于所有字符ch cprefixSum[ch]都需要加上dp[j]因為現在dp[j]代表了以c結尾的新序列這些序列對于未來字符ch c來說都是可以接在后面的“前綴”。但是注意我們更新的是prefixSum[ch]字符維度而不是位置維度。prefixSum[k]的定義是“所有字符 k 的、已處理過的位置的dp值之和”。當我們計算出dp[j]后字符c對應的prefixSum[c_idx]應該增加dp[j]。同時為了后續字符ch c在計算時能包含dp[j]所有ch c對應的prefixSum也需要增加dp[j]。這相當于對prefixSum數組從索引c_idx到末尾進行一次區間加法。我們可以用樹狀數組Fenwick Tree或線段樹Segment Tree來高效維護這個字符維度上的前綴和以及區間更新、單點查詢或者單點更新、前綴查詢取決于定義方式。這樣每次計算dp[j]和更新prefixSum的復雜度可以降到 O(log M)其中 M 是字符集大小如26。整體復雜度優化為 O(n log M)對于 M26幾乎是 O(n)。以下是使用樹狀數組維護“單點更新、前綴查詢”模式的C優化代碼#include iostream #include string #include vector #include cstring using namespace std; const int MOD 1e9 7; const int CHAR_SET 26; // 小寫字母 class Fenwick { private: vectorint tree; int n; public: Fenwick(int size) : n(size), tree(size 1, 0) {} void update(int idx, int delta) { // idx: 字符索引 (0-25) idx; // 樹狀數組通常從1開始 while (idx n) { tree[idx] (tree[idx] delta) % MOD; idx idx -idx; } } int query(int idx) { // 查詢前綴和 [0, idx] idx; int sum 0; while (idx 0) { sum (sum tree[idx]) % MOD; idx - idx -idx; } return sum; } }; int countDistinctIncreasingSubseqFast(string s) { int n s.length(); Fenwick bit(CHAR_SET); int ans 0; for (int j 0; j n; j) { int ch_idx s[j] - a; // 查詢所有嚴格小于當前字符的dp值之和 int sum_less (ch_idx 0) ? 0 : bit.query(ch_idx - 1); // 以s[j]結尾的序列數 1自身 sum_less int dp_j (1 sum_less) % MOD; ans (ans dp_j) % MOD; // 更新樹狀數組當前字符ch_idx對應的dp值增加了dp_j // 注意這里不是直接賦值而是累加。因為bit.query(ch)返回的是所有字符ch的dp和。 // 當我們把dp_j加到bit中ch_idx的位置上后續查詢大于ch_idx的字符時自然也能包含它。 // 但為了嚴格符合“小于”查詢我們只需要更新當前節點。因為后續字符查詢的是前綴和。 // 實際上對于未來字符cc它查詢的是bit.query(c_idx -1)這個和已經包含了我們剛剛更新的dp_j。 // 所以只需要單點更新ch_idx即可。 bit.update(ch_idx, dp_j); } return ans; }這段代碼是優化后的核心。bit.query(ch_idx - 1)高效地得到了我們需要的“小于當前字符的dp和”。bit.update(ch_idx, dp_j)將當前字符新產生的序列數累加到對應的“桶”中供后面的字符使用。4. 完整解題流程與代碼實現現在我們整合前面的分析給出針對藍橋杯風格題目的完整、健壯的解決方案。我們假設題目是標準形式給定一個由小寫字母組成的字符串求本質不同的嚴格上升子序列個數結果對1e97取模。4.1 基礎解法O(n2)適用于 n 5000這是最直觀、最不易出錯的寫法適合在比賽初期快速實現并驗證思路。#include bits/stdc.h using namespace std; const int MOD 1e9 7; int main() { string s; cin s; // 假設輸入字符串 int n s.size(); vectorlong long dp(n, 0); long long ans 0; for (int i 0; i n; i) { dp[i] 1; // 字符本身作為一個序列 for (int j 0; j i; j) { if (s[j] s[i]) { dp[i] (dp[i] dp[j]) % MOD; } } ans (ans dp[i]) % MOD; } cout ans endl; return 0; }4.2 優化解法O(n log 26)適用于 n 10^5使用樹狀數組進行優化這是應對大數據量的標準做法。#include bits/stdc.h using namespace std; const int MOD 1e9 7; const int CHAR_NUM 26; struct Fenwick { vectorint tree; int n; Fenwick(int size) : n(size), tree(size 1, 0) {} void add(int pos, int val) { pos; // 轉為1-indexed while (pos n) { tree[pos] (tree[pos] val) % MOD; pos pos -pos; } } int sum(int pos) { if (pos 0) return 0; // 重要當查詢字符a之前時返回0 pos; int res 0; while (pos 0) { res (res tree[pos]) % MOD; pos - pos -pos; } return res; } }; int main() { string s; cin s; Fenwick bit(CHAR_NUM); int ans 0; for (char c : s) { int idx c - a; // 查詢所有嚴格小于當前字符的dp值之和 int pre_sum bit.sum(idx - 1); // 當前字符結尾的序列總數 1(自身) pre_sum int current (1 pre_sum) % MOD; ans (ans current) % MOD; // 將當前值加入樹狀數組供后續字符使用 bit.add(idx, current); } cout ans endl; return 0; }4.3 測試與驗證編寫代碼后必須用多種案例測試邊界測試空字符串應輸出0但題目一般不會給空串。單字符字符串如a應輸出1。所有字符相同如zzzz嚴格上升序列只有每個字符自身所以答案是字符串長度 n。功能測試ab序列有a,b,ab答案為3。aab如前所述序列有a0,a1,b,ab(0,2),ab(1,2)答案為5。abc所有可能子序列除空序列外都是嚴格上升的。長度為1的3個長度為2的3個ab,ac,bc長度為3的1個abc共7個。也可以用公式 2^n - 1 驗證n3, 2^3-17。性能測試生成一個長字符串如10000個隨機小寫字母用優化版代碼運行應能在短時間內得出結果。5. 常見陷阱、疑難解答與擴展思考即使理解了算法實現時也可能踩坑。下面是一些常見問題和進階思考。5.1 為什么初始化dp[i] 1這代表每個字符本身構成一個長度為1的子序列。這是所有上升子序列的“起點”。在狀態轉移中當s[j]接在某個序列后時我們是在延長已有的序列。如果沒有這個初始的“1”我們就無法生成那些以j開頭實際上是作為序列唯一元素的子序列。5.2 “本質不同”到底是如何通過DP保證的這是最核心的理解點。DP狀態dp[i]的物理意義是“以第 i 個字符結尾的所有本質不同上升子序列的集合的大小”。這個定義的關鍵在于“以第 i 個字符結尾”。任何兩個不同的序列只要它們最后一個字符的索引不同就一定屬于不同的dp[i]。如果它們最后一個字符索引相同但序列本身不同那么它們都是同一個dp[i]所計數的不同對象。在轉移時dp[j] dp[i]意味著我們把dp[i]集合里的每一個序列都復制一份并在末尾追加s[j]然后將這些新序列全部放入dp[j]集合。由于dp[i]集合里的序列彼此不同復制追加后得到的新序列也必然彼此不同。同時對于不同的i即使s[i]相同它們對應的序列集合也是不同的因為結尾索引不同所以貢獻給dp[j]的序列也不會重復。這就保證了從源頭dp[i]集合到終點dp[j]集合的映射是一對一的沒有重復。5.3 如果字符串包含大寫字母、數字或更大字符集怎么辦我們的優化算法依賴于字符集大小 M。對于小寫字母M26對于大寫字母也是26對于數字0-9M10。如果字符集擴大到所有ASCII可見字符約100個O(n log M)依然高效。如果字符集非常大比如整個Unicode樹狀數組的大小和效率就成了問題。此時有幾種思路離散化坐標壓縮先將字符串中所有出現的字符去重排序映射到從0開始的連續整數。這樣字符集大小 M 就等于字符串中不同字符的個數最壞情況是 n但通常遠小于完整的Unicode集。然后再用樹狀數組。使用平衡樹或數組代替樹狀數組如果離散化后M仍然很大接近n那么 O(n log M) 約等于 O(n log n)也是可以接受的。可以直接用std::map或std::set來維護前綴和但常數較大。回到O(n2)DP如果 n 本身不大幾千以內直接用基礎DP更省事。5.4 如何輸出具體的序列而不僅僅是計數這是一個經典的擴展問題。DP只能計數要輸出所有序列必須結合回溯。我們可以修改dp數組讓它存儲一個“序列列表”的引用但這會消耗巨大內存序列數量是指數級的。通常題目不會要求輸出所有可能只要求輸出第K大的序列等。這需要結合DP計數和字典序搜索類似第K小子序列問題復雜度會更高。5.5 內存與溢出問題取模如前所述隨時取模。數據類型即使取模在累加過程中中間變量也可能超出int范圍例如兩個int相加后再取模相加時可能溢出。因此在C中可以使用long long類型進行中間計算或者確保加法和乘法后立即取模。在dp[i]和ans的累加時使用(a b) % MOD的寫法是安全的因為a和b都是已經取過模的數它們的和小于2*MOD不會溢出int如果MOD是1e972*MOD約等于2e914仍在int范圍內約21億。但為了保險比賽時常用long long。負數取模在C中(-1) % MOD結果是-1。如果需要得到非負余數可以(a % MOD MOD) % MOD。但在我們的算法中所有運算都是加法不會產生負數。5.6 一個綜合性的調試案例假設字符串是cba。按照嚴格上升定義沒有任何一個字符對滿足s[i] s[j](ij)。所以dp[0] 1(c)dp[1] 1(b)因為s[0](c) s[1](b)不滿足s[i] s[j]所以不加dp[0]。dp[2] 1(a)同理s[0]和s[1]都大于a。總答案 3。正確因為只有三個單字符子序列。通過這個小例子可以驗證轉移條件s[i] s[j]是否正確應用。