序列比較算法01從串到子序列串與子序列的定義在序列算法中，串是指連續(xù)的字符序列，而子序列則允許字符之間有間隔。例如，'abc'是'abracadabra'的子序列，但不是子串。子序列的生成方式子序列可以通過從原始串中刪除若干字符（可以是零個(gè)）得到，而不需要保持字符的連續(xù)性。這為序列比較提供了靈活性。真子序列的概念當(dāng)一個(gè)子序列不等于原串時(shí)，我們稱其為真子序列。例如，'ab'是'abc'的真子序列，因?yàn)樗鼑?yán)格包含于原串。串與子序列的本質(zhì)差異02編輯距離透視Levenshtein距離三元操作三種基本操作編輯距離算法基于三種基本操作：替換、插入和刪除。這些操作的代價(jià)通常用Levenshtein度量來衡量，滿足三角不等式，確保計(jì)算的合理性。動(dòng)態(tài)規(guī)劃遞推式010203遞推式的邊界條件遞推式的內(nèi)部邏輯遞推式的正確性當(dāng)一個(gè)串為空時(shí)，編輯距離等于另一個(gè)串的長度，因?yàn)橹荒芡ㄟ^插入或刪除操作將其轉(zhuǎn)換為空串。這是遞推式的邊界條件。對(duì)于非空串，遞推式通過比較字符是否相等，選擇最小的編輯操作代價(jià)。如果字符相等，則不需要操作；否則，考慮插入、刪除或替換的代價(jià)。通過歸納法證明遞推式的正確性，確保在每一步都能找到最優(yōu)的編輯操作序列，從而得到兩個(gè)串之間的最小編輯距離。雙循環(huán)算法與回溯構(gòu)造01動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)使用雙循環(huán)遍歷兩個(gè)串，填充動(dòng)態(tài)規(guī)劃表。每個(gè)單元格表示兩個(gè)子串之間的編輯距離，通過比較字符和選擇最小代價(jià)來更新表。02回溯構(gòu)造最優(yōu)解從動(dòng)態(tài)規(guī)劃表的最后一個(gè)單元格開始回溯，根據(jù)表中的值構(gòu)造最優(yōu)編輯序列。這可以通過跟蹤操作路徑來實(shí)現(xiàn)，輸出具體的插入、刪除和替換操作。空間壓縮至線性技巧通過只保留當(dāng)前行和前一行的值，可以將空間復(fù)雜度從O(nm)降低到O(min(n,m))，從而提高算法的效率?？臻g優(yōu)化技巧03最長公共遞增子序列LCS與LIS的融合模型問題定義示例說明最長公共單調(diào)子序列問題結(jié)合了最長公共子序列（LCS）和最長遞增子序列（LIS）的特點(diǎn)，要求找到兩個(gè)序列的公共子序列，且該子序列嚴(yán)格遞增。例如，序列'123'和'135'的最長公共遞增子序列是'13'，因?yàn)樗瑫r(shí)滿足公共子序列和嚴(yán)格遞增的條件。定義f[i][j]為以x[i-1]和y[j-1]結(jié)尾的最長公共遞增子序列的長度，狀態(tài)轉(zhuǎn)移需要考慮字符匹配和遞增條件。狀態(tài)定義當(dāng)x[i-1]等于y[j-1]時(shí)，匹配成功，狀態(tài)轉(zhuǎn)移需要在前面的子序列中找到最大值，確保遞增性。匹配規(guī)則狀態(tài)更新時(shí)，需要考慮匹配點(diǎn)之前的最長公共遞增子序列長度，并在此基礎(chǔ)上加1，以保持遞增性。狀態(tài)更新定理9.2遞歸式證明通過歸納法證明遞歸式的正確性，首先考慮空序列的情況，然后擴(kuò)展到非空序列，確保每一步都滿足最優(yōu)子結(jié)構(gòu)。遞歸式證明思路證明任何可行的最長公共遞增子序列長度不超過遞歸式給出的最大值，并構(gòu)造性地證明存在等于該值的序列。雙向不等式論證雙重循環(huán)實(shí)現(xiàn)與復(fù)雜度算法實(shí)現(xiàn)使用雙重循環(huán)遍歷兩個(gè)序列，維護(hù)當(dāng)前前綴的最大值，通過狀態(tài)轉(zhuǎn)移計(jì)算最長公共遞增子序列的長度。時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度為O(nm)，其中n和m分別是兩個(gè)序列的長度，因?yàn)樾枰闅v兩個(gè)序列的每個(gè)字符?？臻g復(fù)雜度算法的空間復(fù)雜度為O(nm)，用于存儲(chǔ)動(dòng)態(tài)規(guī)劃表?？梢酝ㄟ^滾動(dòng)數(shù)組技術(shù)優(yōu)化到O(min(n,m))。01020304帶約束的LCS子串包含約束需求背景在生物信息學(xué)中，測量基因序列的相似性時(shí)，某些關(guān)鍵DNA片段必須完整出現(xiàn)，這需要考慮帶有子串包含約束的最長公共子序列問題。01帶約束的LCS問題要求在公共子序列中必須包含給定的子串，這改變了最優(yōu)解的結(jié)構(gòu)，需要特殊的算法來解決。

02約束的影響應(yīng)用場景后綴約束動(dòng)態(tài)規(guī)劃模型01定義g[i][j]為x前i個(gè)字符和y前j個(gè)字符且以約束串P為后綴的最長公共子序列長度，狀態(tài)轉(zhuǎn)移需要考慮后綴約束。狀態(tài)定義02根據(jù)字符匹配情況和后綴約束，設(shè)計(jì)遞推式，考慮四種末端情形：直接匹配、僅刪x、僅刪y、無法匹配。遞推式設(shè)計(jì)03邊界條件是當(dāng)序列為空時(shí)，g[i][j]的值，這為遞推提供了初始狀態(tài)，確保算法的正確性。邊界條件子串任意位置拆分策略問題拆分將全局問題拆分為兩段：前段以約束串P為后綴，后段做無約束LCS。通過枚舉P在x與y中的結(jié)束位置，利用已計(jì)算的值求解。時(shí)間復(fù)雜度總時(shí)間復(fù)雜度為O(nm+(n+m)r)，其中n、m是序列長度，r是約束串長度，通過分階段最優(yōu)化實(shí)現(xiàn)高效計(jì)算。05排斥約束的對(duì)偶子串排斥約束定義問題定義最長公共子序列不得包含給定串P作為子串，這是帶約束LCS的對(duì)偶問題，需要排除非法子串。示例說明例如，序列'abc'和'acd'的最長公共子序列是'ac'，但如果約束串是'ab'，則'ac'是不含'ab'的最長公共子序列。狀態(tài)與σ函數(shù)設(shè)計(jì)定義h[i][j][k]為x前i個(gè)字符、y前j個(gè)字符且當(dāng)前已匹配P的前k字符的最長公共子序列長度，狀態(tài)轉(zhuǎn)移需要考慮σ函數(shù)。狀態(tài)定義σ函數(shù)用于計(jì)算字符串與約束串P的最長公共前后綴長度，幫助在狀態(tài)轉(zhuǎn)移時(shí)快速判斷是否觸發(fā)非法子串。σ函數(shù)的作用狀態(tài)轉(zhuǎn)移通過σ函數(shù)在O(1)時(shí)間內(nèi)完成新狀態(tài)的失敗回退，確保在每一步都能避免非法子串的出現(xiàn)。遞歸式與邊界條件邊界條件邊界條件統(tǒng)一設(shè)為-∞或0，以區(qū)分不可達(dá)與可空串，確保最終取最大值時(shí)自動(dòng)過濾非法路徑。當(dāng)x[i-1]等于y[j-1]且加入后不會(huì)使k等于P的長度時(shí)，允許狀態(tài)轉(zhuǎn)移；否則只能分別刪除x或y。遞歸式設(shè)計(jì)O(nm|P|)實(shí)現(xiàn)與總結(jié)算法實(shí)現(xiàn)使用三重循環(huán)實(shí)現(xiàn)算法，最外層k遍歷P的前綴長度，內(nèi)層i、j做二維DP?？臻g優(yōu)化空間復(fù)雜度可滾動(dòng)至O(m|P|)，通過滾動(dòng)數(shù)組技術(shù)減少內(nèi)存占用，提高算法的實(shí)用性。算法總結(jié)帶約束LCS和排斥約束LCS的復(fù)雜度同階，揭示了約束與對(duì)偶約束在算法層面的對(duì)稱性，為序列比較提供了統(tǒng)一的方法論。06小結(jié)編輯距離編輯距離算法通過動(dòng)態(tài)規(guī)劃計(jì)算兩個(gè)序列之間的最小編輯操作次數(shù)，時(shí)間復(fù)雜度為O(nm)，空間復(fù)雜度可優(yōu)化至O(min(n,m))。最長公共遞增子序列最長公共遞增子序列結(jié)合了LCS和LIS的特點(diǎn)，要求公共子序列嚴(yán)格遞增，時(shí)間復(fù)雜度為O(nm)，空間復(fù)雜度為O(nm)。帶約束LCS帶約束LCS問題要求公共子序列包含或排斥給定子串，時(shí)間復(fù)雜度為O(nm|P