1. 項(xiàng)目概述一道經(jīng)典的動(dòng)態(tài)規(guī)劃計(jì)數(shù)題最近在整理藍(lán)橋杯的歷年真題特別是國(guó)賽B組的題目發(fā)現(xiàn)“本質(zhì)上升序列”這道題試題 D的出鏡率相當(dāng)高也經(jīng)常被拿出來(lái)作為動(dòng)態(tài)規(guī)劃DP和字符串處理的經(jīng)典例題來(lái)討論。很多剛接觸算法競(jìng)賽的同學(xué)一看到“上升序列”、“不同子序列”這些詞就容易發(fā)懵感覺(jué)概念纏繞在一起理不清頭緒。這道題恰恰是一個(gè)很好的切入點(diǎn)它不像一些復(fù)雜的圖論或數(shù)論題那樣需要深厚的數(shù)學(xué)背景而是更考驗(yàn)我們對(duì)問(wèn)題本質(zhì)的抽象能力和對(duì)DP狀態(tài)定義的精準(zhǔn)把握。簡(jiǎn)單來(lái)說(shuō)題目會(huì)給你一個(gè)字符串比如lanqiao要求你找出這個(gè)字符串中所有的“本質(zhì)不同的上升子序列”的個(gè)數(shù)。這里有兩個(gè)關(guān)鍵約束“本質(zhì)不同”和“上升”?！吧仙痹谧址恼Z(yǔ)境下通常指的是子序列中字符的索引是嚴(yán)格遞增的這是子序列的天然定義一般無(wú)需特別處理。而“本質(zhì)不同”則意味著即使兩個(gè)子序列由相同的字符組成只要它們?cè)谠址械奈恢盟饕煌捅灰暈椴煌男蛄?。這才是題目的核心難點(diǎn)和考點(diǎn)它要求我們計(jì)數(shù)時(shí)必須基于字符在原串中的位置來(lái)區(qū)分而不能僅僅看字符本身。舉個(gè)例子字符串a(chǎn)ab。如果只考慮由字符組成的子序列a出現(xiàn)了兩次但這兩個(gè)a來(lái)自原串中不同位置索引0和索引1因此它們是兩個(gè)不同的“本質(zhì)上升序列”。同樣ab也有兩個(gè)一個(gè)由索引0的a和索引2的b組成另一個(gè)由索引1的a和索引2的b組成。所以總數(shù)為 2單個(gè)a 2ab 1單個(gè)b 5。如果錯(cuò)誤地按字符集去重就會(huì)得到錯(cuò)誤結(jié)果。解決這類問(wèn)題暴力枚舉所有子序列顯然不可行時(shí)間復(fù)雜度 O(2^n)。標(biāo)準(zhǔn)的解法是使用動(dòng)態(tài)規(guī)劃。但具體怎么定義狀態(tài)怎么轉(zhuǎn)移怎么保證計(jì)數(shù)不重不漏里面有不少細(xì)節(jié)和技巧。接下來(lái)我就結(jié)合自己的解題和教學(xué)經(jīng)驗(yàn)把這道題從思路到代碼再到各種變體和坑點(diǎn)徹底拆解清楚。2. 核心思路解析與動(dòng)態(tài)規(guī)劃狀態(tài)設(shè)計(jì)面對(duì)“本質(zhì)不同的上升子序列計(jì)數(shù)”問(wèn)題我們首先要摒棄“先找出所有子序列再去重”的暴力想法。動(dòng)態(tài)規(guī)劃的精髓在于利用已計(jì)算的信息高效地遞推出新的信息。我們的目標(biāo)是設(shè)計(jì)一個(gè)DP狀態(tài)使得在遞推過(guò)程中天然地滿足“本質(zhì)不同”和“上升”的要求。2.1 為什么是動(dòng)態(tài)規(guī)劃字符串子序列計(jì)數(shù)問(wèn)題尤其是要求“不同”的計(jì)數(shù)非常適合用DP解決。因?yàn)樽有蛄械纳删哂忻黠@的階段性按原串順序逐個(gè)考慮字符并且后一個(gè)字符能否接在前面的序列之后只取決于前面序列的最后一個(gè)字符或者更廣義地說(shuō)最后一個(gè)字符的位置和大小。這滿足了DP的“無(wú)后效性”條件。2.2 狀態(tài)定義的藝術(shù)最直接的想法是定義dp[i]表示“以第i個(gè)字符結(jié)尾的本質(zhì)不同的上升子序列”的個(gè)數(shù)。這個(gè)定義很直觀但存在一個(gè)重大問(wèn)題當(dāng)我們?cè)诤罄m(xù)位置j (j i)考慮字符s[j]時(shí)如果s[j] s[i]那么s[j]可以接在所有以s[i]結(jié)尾的子序列后面形成新的子序列。但是不同的i可能對(duì)應(yīng)相同的字符s[i]。例如aab有兩個(gè)a。以第一個(gè)a結(jié)尾的序列有{a}以第二個(gè)a結(jié)尾的序列也有{a}。如果我們簡(jiǎn)單地將dp[j]加上所有滿足s[i] s[j]的dp[i]那么對(duì)于s[j] b它會(huì)同時(shí)加上dp[0]和dp[1]都是1從而認(rèn)為可以形成兩個(gè)ab。這看起來(lái)是對(duì)的但這里隱藏了重復(fù)計(jì)數(shù)的問(wèn)題嗎讓我們深入思考“本質(zhì)不同”。序列ab有兩個(gè)分別是(索引0, 索引2)和(索引1, 索引2)。在我們的計(jì)算中dp[2]對(duì)應(yīng)字符b 應(yīng)該最終等于2代表以b結(jié)尾的序列有兩個(gè)ab來(lái)自第一個(gè)a和ab來(lái)自第二個(gè)a。但是dp[i]本身表示“以 i 結(jié)尾”的序列數(shù)這個(gè)定義已經(jīng)隱含了位置信息。所以只要我們?cè)谵D(zhuǎn)移時(shí)讓dp[j]累加所有i j 且 s[i] s[j]的dp[i]那么來(lái)自不同i的貢獻(xiàn)自然就是不同的序列因?yàn)樗鼈兘Y(jié)尾的a的位置不同。然而還有一個(gè)更棘手的問(wèn)題單個(gè)字符構(gòu)成的子序列。按照dp[i]的定義它包含了以i結(jié)尾的所有序列這自然也包括長(zhǎng)度為1的序列即字符s[i]本身。那么dp[i]的初始值應(yīng)該是什么如果設(shè)為1代表序列{s[i]}本身那么在轉(zhuǎn)移時(shí)dp[j]累加dp[i]時(shí)就會(huì)把{s[i]}這個(gè)序列后面加上s[j]形成{s[i], s[j]}這是正確的。但是最終的總數(shù)如果簡(jiǎn)單地將所有dp[i]相加會(huì)不會(huì)重復(fù)計(jì)算不會(huì)因?yàn)槊總€(gè)dp[i]計(jì)數(shù)的是以特定位置i結(jié)尾的序列它們彼此互斥。所以狀態(tài)定義dp[i]是可行的。最終答案就是sum(dp[0], dp[1], ..., dp[n-1])其中n是字符串長(zhǎng)度。2.3 狀態(tài)轉(zhuǎn)移方程的推導(dǎo)基于狀態(tài)dp[i]以字符串中第i個(gè)位置索引從0開(kāi)始的字符結(jié)尾的、本質(zhì)不同的嚴(yán)格上升子序列的個(gè)數(shù)。初始化對(duì)于每個(gè)位置i至少有一個(gè)以其自身結(jié)尾的、長(zhǎng)度為1的子序列。因此dp[i]的初始值為 1。轉(zhuǎn)移方程對(duì)于當(dāng)前位置j我們需要考慮所有在它之前的位置i (0 i j)。如果s[i] s[j]注意題目中的“上升”在字符序列中通常指字典序或數(shù)值序?qū)τ谛懽帜妇褪茿SCII碼的大小那么所有以s[i]結(jié)尾的上升子序列在其末尾添加上s[j]后仍然是一個(gè)上升子序列并且由于結(jié)尾變成了j這個(gè)新序列自然是以j結(jié)尾的。因此轉(zhuǎn)移方程為dp[j] 1 sum(dp[i])其中i滿足0 i j且s[i] s[j]。這里的1代表長(zhǎng)度為1的子序列即s[j]本身。sum(dp[i])代表了所有能以s[j]接在后面形成更長(zhǎng)序列的情況。關(guān)鍵點(diǎn)為什么這樣能保證“本質(zhì)不同”因?yàn)閐p[i]中的每個(gè)序列都由其具體的字符索引路徑唯一確定。當(dāng)s[j]接在某個(gè)以i結(jié)尾的特定序列后面時(shí)產(chǎn)生的新序列的路徑是原路徑加上j這個(gè)路徑是唯一的。即使兩個(gè)不同的i1和i2對(duì)應(yīng)的字符相同s[i1] s[i2]但由于i1 ! i2它們所代表的“以該位置結(jié)尾的序列集合”是不同的因此貢獻(xiàn)給dp[j]的序列也是不同的。2.4 復(fù)雜度分析與初步實(shí)現(xiàn)根據(jù)上述方程我們需要對(duì)每個(gè)j遍歷所有i j。這是一個(gè)典型的雙重循環(huán)結(jié)構(gòu)。時(shí)間復(fù)雜度O(n2)其中 n 是字符串長(zhǎng)度。對(duì)于藍(lán)橋杯的題目字符串長(zhǎng)度一般控制在幾百到幾千O(n2) 通常是可接受的。空間復(fù)雜度O(n)用于存儲(chǔ)dp數(shù)組。一個(gè)最基礎(chǔ)的C實(shí)現(xiàn)框架如下#include iostream #include string #include vector using namespace std; int countDistinctIncreasingSubseq(string s) { int n s.length(); vectorlong long dp(n, 0); // 使用long long防止大數(shù)溢出 long long ans 0; for (int j 0; j n; j) { dp[j] 1; // 初始化自身作為一個(gè)序列 for (int i 0; i j; i) { if (s[i] s[j]) { dp[j] dp[i]; } } ans dp[j]; } return ans; // 注意ans可能很大題目可能要求取模 }這就是最核心的解法。但是這道題的魅力和坑點(diǎn)遠(yuǎn)不止于此。上面的解法是基礎(chǔ)但在實(shí)際競(jìng)賽中可能會(huì)遇到各種變體和需要優(yōu)化的地方。3. 細(xì)節(jié)深化、優(yōu)化與變體分析掌握了基礎(chǔ)DP解法我們才算剛剛?cè)腴T。在實(shí)際應(yīng)用中尤其是面對(duì)藍(lán)橋杯這種對(duì)效率和正確性要求極高的競(jìng)賽我們需要考慮更多。3.1 處理大數(shù)與取模問(wèn)題藍(lán)橋杯的題目往往不滿足于小規(guī)模數(shù)據(jù)。當(dāng)字符串長(zhǎng)度達(dá)到幾千且字符分布較均勻時(shí)本質(zhì)上升序列的數(shù)量會(huì)呈指數(shù)級(jí)增長(zhǎng)很容易超出int甚至long long的范圍。因此題目經(jīng)常會(huì)要求對(duì)結(jié)果取模例如1e9 7。注意取模運(yùn)算必須在加法和乘法過(guò)程中隨時(shí)進(jìn)行防止中間結(jié)果溢出。同時(shí)要特別注意負(fù)數(shù)取模的問(wèn)題在C中%運(yùn)算符對(duì)負(fù)數(shù)取模的結(jié)果是負(fù)數(shù)需要調(diào)整。修改后的代碼需加入取模const int MOD 1e9 7; int countDistinctIncreasingSubseq(string s) { int n s.length(); vectorint dp(n, 0); // 改用int因?yàn)闀?huì)取模 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 當(dāng)“上升”定義變化時(shí)我們之前的討論基于s[i] s[j]這是最常見(jiàn)的字典序ASCII碼嚴(yán)格上升。但如果題目變體呢非嚴(yán)格上升不下降即允許s[i] s[j]。這時(shí)問(wèn)題會(huì)變得更復(fù)雜因?yàn)橐幚硐嗟茸址麕?lái)的重復(fù)計(jì)數(shù)。自定義順序例如規(guī)定a z b y這種非常規(guī)順序。這時(shí)只需將比較條件s[i] s[j]替換為一個(gè)自定義的比較函數(shù)即可。重點(diǎn)討論非嚴(yán)格上升如果允許相等那么當(dāng)s[i] s[j]時(shí)以i結(jié)尾的序列后面加上s[j]會(huì)形成一個(gè)新的以j結(jié)尾的序列。但是這里必須非常小心地處理重復(fù)例如字符串a(chǎn)a。按照樸素想法dp[0] 1(序列a0)計(jì)算dp[1]i0, s[0]a s[1]所以dp[1] 1 dp[0] 2。這表示以第二個(gè)a結(jié)尾的序列有{a1}和{a0, a1}?？偞鸢?dp[0] dp[1] 3。但實(shí)際上序列有哪些{a0},{a1},{a0, a1}。這看起來(lái)是對(duì)的。但再看aba按上述邏輯計(jì)算最終會(huì)包含{a0, a2}和{a1, a2}嗎注意s[2]是as[0]和s[1]都是a且s[0] s[2]?不是等于。所以按照s[i] s[j]它們應(yīng)該被計(jì)入。但{a0, a2}和{a1, a2}是本質(zhì)不同的嗎是的因?yàn)橹虚g的字符索引不同。所以算法似乎仍然有效這里有一個(gè)巨大的陷阱?？紤]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。但我們手動(dòng)枚舉所有非嚴(yán)格上升子序列a0a1a2a0, a1a0, a2a1, a2a0, a1, a2正好7個(gè)?？雌饋?lái)沒(méi)錯(cuò)。但是如果我們改變計(jì)算順序或者深究DP的定義會(huì)發(fā)現(xiàn)這個(gè)樸素加法在更復(fù)雜的情況下會(huì)導(dǎo)致重復(fù)計(jì)算。問(wèn)題出在哪里出在當(dāng)s[i] s[j]時(shí)dp[j]直接加上了dp[i]。這意味著所有以i結(jié)尾的序列都復(fù)制了一份到j(luò)的名下并把結(jié)尾改為j。這在i和j之間沒(méi)有其他相等字符時(shí)是可行的。但如果有多個(gè)相等的字符就會(huì)重復(fù)。更嚴(yán)謹(jǐn)?shù)淖龇ㄊ菍?duì)于非嚴(yán)格上升我們需要保證對(duì)于相同的字符只在最后一次出現(xiàn)時(shí)計(jì)算所有以其結(jié)尾的序列。否則同一個(gè)序列會(huì)因?yàn)榭梢酝ㄟ^(guò)不同位置的相同字符作為“最后一步”而產(chǎn)生多次貢獻(xiàn)。正確的狀態(tài)定義需要改變dp[i]表示以第 i 個(gè)位置結(jié)尾的本質(zhì)不同的非下降子序列個(gè)數(shù)但在轉(zhuǎn)移時(shí)對(duì)于字符ch我們只應(yīng)該從上一個(gè)字符ch出現(xiàn)的位置轉(zhuǎn)移過(guò)來(lái)而不是所有更早的位置。這通常需要維護(hù)一個(gè)last[ch]數(shù)組記錄字符ch上一次出現(xiàn)時(shí)的DP值總和。當(dāng)遇到新的s[j]時(shí)dp[j] 1 sum(dp[i] for all i j where s[i] s[j])但需要減去之前相同字符已經(jīng)計(jì)算過(guò)的部分。這變得非常復(fù)雜。實(shí)操心得在競(jìng)賽中如果遇到“非嚴(yán)格上升”的計(jì)數(shù)一定要先用手動(dòng)枚舉小例子如”aa“”aab“”aba“”aaa“驗(yàn)證自己的DP方程是否正確。通常這類問(wèn)題會(huì)轉(zhuǎn)化為對(duì)每個(gè)字符維護(hù)一個(gè)累積和并利用容斥原理來(lái)避免重復(fù)。一個(gè)常見(jiàn)的技巧是定義dp[j]為以s[j]結(jié)尾的序列數(shù)同時(shí)維護(hù)一個(gè)sum[ch]表示當(dāng)前以字符ch結(jié)尾的所有序列總數(shù)。當(dāng)處理到s[j]時(shí)dp[j] 1 sum(sum[ch])其中ch遍歷所有小于等于s[j]的字符。然后更新sum[s[j]] dp[j]注意這里是賦值不是累加因?yàn)樾碌膁p[j]已經(jīng)包含了所有以小于等于s[j]的字符結(jié)尾的序列后面接上s[j]的情況而舊的sum[s[j]]對(duì)應(yīng)的那些序列的結(jié)尾位置更早它們已經(jīng)包含在新的dp[j]的生成路徑中了如果累加就會(huì)重復(fù)。最后答案就是所有sum[ch]的總和。這種方法可以將復(fù)雜度優(yōu)化到 O(n * 字符集大小)。3.3 算法優(yōu)化從 O(n2) 到 O(n log n) 或 O(n * 26)對(duì)于基礎(chǔ)DP的 O(n2) 算法當(dāng) n 達(dá)到 10^5 時(shí)就不行了。我們需要優(yōu)化內(nèi)層循環(huán)——即快速求出“所有在j之前且字符小于s[j]的dp[i]之和”。這本質(zhì)上是一個(gè)動(dòng)態(tài)前綴和問(wèn)題。字符集通常是有限的如小寫字母26個(gè)。我們可以維護(hù)一個(gè)數(shù)組prefixSum[26]其中prefixSum[k]表示當(dāng)前所有字符小于等于char(ak)的、且位置在j之前的dp[i]值的總和。那么對(duì)于當(dāng)前位置j的字符c我們需要所有字符嚴(yán)格小于c的dp值之和即prefixSum[c - a - 1]如果c是a則為0。然后dp[j] 1 這個(gè)和。更新prefixSum數(shù)組對(duì)于所有字符ch cprefixSum[ch]都需要加上dp[j]因?yàn)楝F(xiàn)在dp[j]代表了以c結(jié)尾的新序列這些序列對(duì)于未來(lái)字符ch c來(lái)說(shuō)都是可以接在后面的“前綴”。但是注意我們更新的是prefixSum[ch]字符維度而不是位置維度。prefixSum[k]的定義是“所有字符 k 的、已處理過(guò)的位置的dp值之和”。當(dāng)我們計(jì)算出dp[j]后字符c對(duì)應(yīng)的prefixSum[c_idx]應(yīng)該增加dp[j]。同時(shí)為了后續(xù)字符ch c在計(jì)算時(shí)能包含dp[j]所有ch c對(duì)應(yīng)的prefixSum也需要增加dp[j]。這相當(dāng)于對(duì)prefixSum數(shù)組從索引c_idx到末尾進(jìn)行一次區(qū)間加法。我們可以用樹(shù)狀數(shù)組Fenwick Tree或線段樹(shù)Segment Tree來(lái)高效維護(hù)這個(gè)字符維度上的前綴和以及區(qū)間更新、單點(diǎn)查詢或者單點(diǎn)更新、前綴查詢?nèi)Q于定義方式。這樣每次計(jì)算dp[j]和更新prefixSum的復(fù)雜度可以降到 O(log M)其中 M 是字符集大小如26。整體復(fù)雜度優(yōu)化為 O(n log M)對(duì)于 M26幾乎是 O(n)。以下是使用樹(shù)狀數(shù)組維護(hù)“單點(diǎn)更新、前綴查詢”模式的C優(yōu)化代碼#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; // 樹(shù)狀數(shù)組通常從1開(kāi)始 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; // 查詢所有嚴(yán)格小于當(dāng)前字符的dp值之和 int sum_less (ch_idx 0) ? 0 : bit.query(ch_idx - 1); // 以s[j]結(jié)尾的序列數(shù) 1自身 sum_less int dp_j (1 sum_less) % MOD; ans (ans dp_j) % MOD; // 更新樹(shù)狀數(shù)組當(dāng)前字符ch_idx對(duì)應(yīng)的dp值增加了dp_j // 注意這里不是直接賦值而是累加。因?yàn)閎it.query(ch)返回的是所有字符ch的dp和。 // 當(dāng)我們把dp_j加到bit中ch_idx的位置上后續(xù)查詢大于ch_idx的字符時(shí)自然也能包含它。 // 但為了嚴(yán)格符合“小于”查詢我們只需要更新當(dāng)前節(jié)點(diǎn)。因?yàn)楹罄m(xù)字符查詢的是前綴和。 // 實(shí)際上對(duì)于未來(lái)字符cc它查詢的是bit.query(c_idx -1)這個(gè)和已經(jīng)包含了我們剛剛更新的dp_j。 // 所以只需要單點(diǎn)更新ch_idx即可。 bit.update(ch_idx, dp_j); } return ans; }這段代碼是優(yōu)化后的核心。bit.query(ch_idx - 1)高效地得到了我們需要的“小于當(dāng)前字符的dp和”。bit.update(ch_idx, dp_j)將當(dāng)前字符新產(chǎn)生的序列數(shù)累加到對(duì)應(yīng)的“桶”中供后面的字符使用。4. 完整解題流程與代碼實(shí)現(xiàn)現(xiàn)在我們整合前面的分析給出針對(duì)藍(lán)橋杯風(fēng)格題目的完整、健壯的解決方案。我們假設(shè)題目是標(biāo)準(zhǔn)形式給定一個(gè)由小寫字母組成的字符串求本質(zhì)不同的嚴(yán)格上升子序列個(gè)數(shù)結(jié)果對(duì)1e97取模。4.1 基礎(chǔ)解法O(n2)適用于 n 5000這是最直觀、最不易出錯(cuò)的寫法適合在比賽初期快速實(shí)現(xiàn)并驗(yàn)證思路。#include bits/stdc.h using namespace std; const int MOD 1e9 7; int main() { string s; cin s; // 假設(shè)輸入字符串 int n s.size(); vectorlong long dp(n, 0); long long ans 0; for (int i 0; i n; i) { dp[i] 1; // 字符本身作為一個(gè)序列 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 優(yōu)化解法O(n log 26)適用于 n 10^5使用樹(shù)狀數(shù)組進(jìn)行優(yōu)化這是應(yīng)對(duì)大數(shù)據(jù)量的標(biāo)準(zhǔn)做法。#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; // 轉(zhuǎn)為1-indexed while (pos n) { tree[pos] (tree[pos] val) % MOD; pos pos -pos; } } int sum(int pos) { if (pos 0) return 0; // 重要當(dāng)查詢字符a之前時(shí)返回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; // 查詢所有嚴(yán)格小于當(dāng)前字符的dp值之和 int pre_sum bit.sum(idx - 1); // 當(dāng)前字符結(jié)尾的序列總數(shù) 1(自身) pre_sum int current (1 pre_sum) % MOD; ans (ans current) % MOD; // 將當(dāng)前值加入樹(shù)狀數(shù)組供后續(xù)字符使用 bit.add(idx, current); } cout ans endl; return 0; }4.3 測(cè)試與驗(yàn)證編寫代碼后必須用多種案例測(cè)試邊界測(cè)試空字符串應(yīng)輸出0但題目一般不會(huì)給空串。單字符字符串如a應(yīng)輸出1。所有字符相同如zzzz嚴(yán)格上升序列只有每個(gè)字符自身所以答案是字符串長(zhǎng)度 n。功能測(cè)試ab序列有a,b,ab答案為3。aab如前所述序列有a0,a1,b,ab(0,2),ab(1,2)答案為5。abc所有可能子序列除空序列外都是嚴(yán)格上升的。長(zhǎng)度為1的3個(gè)長(zhǎng)度為2的3個(gè)ab,ac,bc長(zhǎng)度為3的1個(gè)abc共7個(gè)。也可以用公式 2^n - 1 驗(yàn)證n3, 2^3-17。性能測(cè)試生成一個(gè)長(zhǎng)字符串如10000個(gè)隨機(jī)小寫字母用優(yōu)化版代碼運(yùn)行應(yīng)能在短時(shí)間內(nèi)得出結(jié)果。5. 常見(jiàn)陷阱、疑難解答與擴(kuò)展思考即使理解了算法實(shí)現(xiàn)時(shí)也可能踩坑。下面是一些常見(jiàn)問(wèn)題和進(jìn)階思考。5.1 為什么初始化dp[i] 1這代表每個(gè)字符本身構(gòu)成一個(gè)長(zhǎng)度為1的子序列。這是所有上升子序列的“起點(diǎn)”。在狀態(tài)轉(zhuǎn)移中當(dāng)s[j]接在某個(gè)序列后時(shí)我們是在延長(zhǎng)已有的序列。如果沒(méi)有這個(gè)初始的“1”我們就無(wú)法生成那些以j開(kāi)頭實(shí)際上是作為序列唯一元素的子序列。5.2 “本質(zhì)不同”到底是如何通過(guò)DP保證的這是最核心的理解點(diǎn)。DP狀態(tài)dp[i]的物理意義是“以第 i 個(gè)字符結(jié)尾的所有本質(zhì)不同上升子序列的集合的大小”。這個(gè)定義的關(guān)鍵在于“以第 i 個(gè)字符結(jié)尾”。任何兩個(gè)不同的序列只要它們最后一個(gè)字符的索引不同就一定屬于不同的dp[i]。如果它們最后一個(gè)字符索引相同但序列本身不同那么它們都是同一個(gè)dp[i]所計(jì)數(shù)的不同對(duì)象。在轉(zhuǎn)移時(shí)dp[j] dp[i]意味著我們把dp[i]集合里的每一個(gè)序列都復(fù)制一份并在末尾追加s[j]然后將這些新序列全部放入dp[j]集合。由于dp[i]集合里的序列彼此不同復(fù)制追加后得到的新序列也必然彼此不同。同時(shí)對(duì)于不同的i即使s[i]相同它們對(duì)應(yīng)的序列集合也是不同的因?yàn)榻Y(jié)尾索引不同所以貢獻(xiàn)給dp[j]的序列也不會(huì)重復(fù)。這就保證了從源頭dp[i]集合到終點(diǎn)dp[j]集合的映射是一對(duì)一的沒(méi)有重復(fù)。5.3 如果字符串包含大寫字母、數(shù)字或更大字符集怎么辦我們的優(yōu)化算法依賴于字符集大小 M。對(duì)于小寫字母M26對(duì)于大寫字母也是26對(duì)于數(shù)字0-9M10。如果字符集擴(kuò)大到所有ASCII可見(jiàn)字符約100個(gè)O(n log M)依然高效。如果字符集非常大比如整個(gè)Unicode樹(shù)狀數(shù)組的大小和效率就成了問(wèn)題。此時(shí)有幾種思路離散化坐標(biāo)壓縮先將字符串中所有出現(xiàn)的字符去重排序映射到從0開(kāi)始的連續(xù)整數(shù)。這樣字符集大小 M 就等于字符串中不同字符的個(gè)數(shù)最壞情況是 n但通常遠(yuǎn)小于完整的Unicode集。然后再用樹(shù)狀數(shù)組。使用平衡樹(shù)或數(shù)組代替樹(shù)狀數(shù)組如果離散化后M仍然很大接近n那么 O(n log M) 約等于 O(n log n)也是可以接受的。可以直接用std::map或std::set來(lái)維護(hù)前綴和但常數(shù)較大。回到O(n2)DP如果 n 本身不大幾千以內(nèi)直接用基礎(chǔ)DP更省事。5.4 如何輸出具體的序列而不僅僅是計(jì)數(shù)這是一個(gè)經(jīng)典的擴(kuò)展問(wèn)題。DP只能計(jì)數(shù)要輸出所有序列必須結(jié)合回溯。我們可以修改dp數(shù)組讓它存儲(chǔ)一個(gè)“序列列表”的引用但這會(huì)消耗巨大內(nèi)存序列數(shù)量是指數(shù)級(jí)的。通常題目不會(huì)要求輸出所有可能只要求輸出第K大的序列等。這需要結(jié)合DP計(jì)數(shù)和字典序搜索類似第K小子序列問(wèn)題復(fù)雜度會(huì)更高。5.5 內(nèi)存與溢出問(wèn)題取模如前所述隨時(shí)取模。數(shù)據(jù)類型即使取模在累加過(guò)程中中間變量也可能超出int范圍例如兩個(gè)int相加后再取模相加時(shí)可能溢出。因此在C中可以使用long long類型進(jìn)行中間計(jì)算或者確保加法和乘法后立即取模。在dp[i]和ans的累加時(shí)使用(a b) % MOD的寫法是安全的因?yàn)閍和b都是已經(jīng)取過(guò)模的數(shù)它們的和小于2*MOD不會(huì)溢出int如果MOD是1e972*MOD約等于2e914仍在int范圍內(nèi)約21億。但為了保險(xiǎn)比賽時(shí)常用long long。負(fù)數(shù)取模在C中(-1) % MOD結(jié)果是-1。如果需要得到非負(fù)余數(shù)可以(a % MOD MOD) % MOD。但在我們的算法中所有運(yùn)算都是加法不會(huì)產(chǎn)生負(fù)數(shù)。5.6 一個(gè)綜合性的調(diào)試案例假設(shè)字符串是cba。按照嚴(yán)格上升定義沒(méi)有任何一個(gè)字符對(duì)滿足s[i] s[j](ij)。所以dp[0] 1(c)dp[1] 1(b)因?yàn)閟[0](c) s[1](b)不滿足s[i] s[j]所以不加dp[0]。dp[2] 1(a)同理s[0]和s[1]都大于a?？偞鸢? 3。正確因?yàn)橹挥腥齻€(gè)單字符子序列。通過(guò)這個(gè)小例子可以驗(yàn)證轉(zhuǎn)移條件s[i] s[j]是否正確應(yīng)用。