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