LCS問(wèn)題的解決思路
解最長(zhǎng)公共子序列問(wèn)題時(shí)最容易想到的算法是窮舉搜索法，即對(duì)X的每一個(gè)子序列妓羊，檢查它是否也是Y的子序列顶岸，從而確定它是否為X和Y的公共子序列，并且在檢查過(guò)程中選出最長(zhǎng)的公共子序列蝴簇。X和Y的所有子序列都檢查過(guò)后即可求出X和Y的最長(zhǎng)公共子序列。X的一個(gè)子序列相應(yīng)于下標(biāo)序列{1, 2, …, m}的一個(gè)子序列匆帚，因此熬词，X共有2m個(gè)不同子序列（Y亦如此，如為2^n）吸重，從而窮舉搜索法需要指數(shù)時(shí)間（2^m * 2^n）互拾。
動(dòng)態(tài)規(guī)劃算法
??? 事實(shí)上，最長(zhǎng)公共子序列問(wèn)題也有最優(yōu)子結(jié)構(gòu)性質(zhì)晤锹。
記:
Xi=﹤x1摩幔，?，xi﹥即X序列的前i個(gè)字符 (1≤i≤m)（前綴）
Yj=﹤y1鞭铆，?或衡，yj﹥即Y序列的前j個(gè)字符 (1≤j≤n)（前綴）
假定Z=﹤z1，?车遂，zk﹥∈LCS(X , Y)封断。
若xm=yn（最后一個(gè)字符相同），則不難用反證法證明：該字符必是X與Y的任一最長(zhǎng)公共子序列Z（設(shè)長(zhǎng)度為k）的最后一個(gè)字符舶担，即有zk = xm = yn 且顯然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前綴Zk-1是Xm-1與Yn-1的最長(zhǎng)公共子序列坡疼。此時(shí)，問(wèn)題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長(zhǎng)度等于LCS(Xm-1 , Yn-1)的長(zhǎng)度加1）衣陶。
若xm≠yn柄瑰，則亦不難用反證法證明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)剪况。由于zk≠xm與zk≠yn其中至少有一個(gè)必成立教沾，若zk≠xm則有Z∈LCS(Xm-1 , Y)，類似的译断，若zk≠yn 則有Z∈LCS(X , Yn-1)授翻。此時(shí)，問(wèn)題化歸成求Xm-1與Y的LCS及X與Yn-1的LCS。LCS(X , Y)的長(zhǎng)度為：max{LCS(Xm-1 , Y)的長(zhǎng)度, LCS(X , Yn-1)的長(zhǎng)度}堪唐。
由于上述當(dāng)xm≠yn的情況中巡语，求LCS(Xm-1 , Y)的長(zhǎng)度與LCS(X , Yn-1)的長(zhǎng)度，這兩個(gè)問(wèn)題不是相互獨(dú)立的：兩者都需要求LCS(Xm-1淮菠，Yn-1)的長(zhǎng)度男公。另外兩個(gè)序列的LCS中包含了兩個(gè)序列的前綴的LCS，故問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)考慮用動(dòng)態(tài)規(guī)劃法兜材。
也就是說(shuō)理澎，解決這個(gè)LCS問(wèn)題，你要求三個(gè)方面的東西：1曙寡、LCS（Xm-1，Yn-1）+1寇荧；2举庶、LCS（Xm-1，Y）揩抡，LCS（X户侥，Yn-1）；3峦嗤、max{LCS（Xm-1蕊唐，Y），LCS（X烁设，Yn-1）}替梨。
