、最長公共子序列(Longest Common Subsequence:LCS)
設有兩個序列A[1...m]和B[1...n],分別對A和B進行劃分子序列
A[1] A[1..2] A[1..3] ... A[1..m]
B[1] B[1..2] B[1..3] ... B[1..n]
依次求出A中的每個子序列(從A[1]開始)與B中每個子序列的最長公共子序列，並記錄在陣列C[m][n]中，C[i][j]表示A[1..i]和B[1..j]的最長公共子序列的長度。
遞推公式如下：
①C[i][j]=0 i=0 or j=0
②C[i][j]=C[i-1][j-1]+1 i!=0 and j!=0 and A[i]=B[j]
路徑記錄：
記錄路徑即記錄C[i][j]是怎麼得來的，從遞推公式②③知，C[i][j]的來源有三個：C[i-1][j-1],C[i-1][j],C[i][j-1]。如果是從C[i-1][j-1]得來，那麼A[i]=B[j],是最長公共子序列中的一個元素。
可以設定一個數組P[m][n]來記錄當前的C[i][j]是怎麼得來的，P[m][n]的取值只能有三種,分別記為1 2 3。
構造最長公共子序列：
用遞迴的方法，檢查P[i][j]，初始i=m,j=n
如果p[i][j]=1，則記錄C[i][j],然後遞迴處理P[i-1][j-1]
如果P[i][j]=2,不記錄，遞迴處理P[i-1][j]
如果P[i][j]=3,不記錄，遞推處理P[i][j-1]
直到i=0 or j=0
時間複雜度：O(mn)
、最長公共子序列(Longest Common Subsequence:LCS)
設有兩個序列A[1...m]和B[1...n],分別對A和B進行劃分子序列
A[1] A[1..2] A[1..3] ... A[1..m]
B[1] B[1..2] B[1..3] ... B[1..n]
依次求出A中的每個子序列(從A[1]開始)與B中每個子序列的最長公共子序列，並記錄在陣列C[m][n]中，C[i][j]表示A[1..i]和B[1..j]的最長公共子序列的長度。
遞推公式如下：
①C[i][j]=0 i=0 or j=0
②C[i][j]=C[i-1][j-1]+1 i!=0 and j!=0 and A[i]=B[j]
路徑記錄：
記錄路徑即記錄C[i][j]是怎麼得來的，從遞推公式②③知，C[i][j]的來源有三個：C[i-1][j-1],C[i-1][j],C[i][j-1]。如果是從C[i-1][j-1]得來，那麼A[i]=B[j],是最長公共子序列中的一個元素。
可以設定一個數組P[m][n]來記錄當前的C[i][j]是怎麼得來的，P[m][n]的取值只能有三種,分別記為1 2 3。
構造最長公共子序列：
用遞迴的方法，檢查P[i][j]，初始i=m,j=n
如果p[i][j]=1，則記錄C[i][j],然後遞迴處理P[i-1][j-1]
如果P[i][j]=2,不記錄，遞迴處理P[i-1][j]
如果P[i][j]=3,不記錄，遞推處理P[i][j-1]
直到i=0 or j=0
時間複雜度：O(mn)