子序列

一個序列A ＝ a1,a2,……an,中任意刪除若干項线欲，剩余的序列叫做A的一個子序列。也可以認為是從序列A按原順序保留任意若干項得到的序列趴泌。

對序列 1,3,5,4,2,6,8,7來說氏仗，序列3,4,8,7 是它的一個子序列呐舔。
對于一個長度為n的序列，它一共有 個子序列，有個非空子序列。
請注意：子序列不是子集，它和原始序列的元素順序是相關的

公共子序列

顧名思義盅视，如果序列C既是序列A的子序列，同時也是序列B的子序列，則稱它為序列A和序列B的公共子序列。

空序列是任何兩個序列的公共子序列

最長公共子序列

A和B的公共子序列中長度最長的（包含元素最多的）叫做A和B的公共子序列

最長公共子序列示意圖

描述：最長公共子序列問題就是求序列, 和,的一個最長公共子序列

用表示序列A的連續(xù)前x項構成的子序列埃撵，即, , 我們用表示它們的最長公共子序列長度谣拣，那原問題等價于求LCS(m,n)苛谷。為了方便我們用表示和的一個最長公共子序列

• 令表示子序列考慮最后一項
  (1)

  • 那么它們的最后一項一定是這個元素锣尉，為了方便树瞭，我們令, 我們用反證法：假設最后一項不是凉敲，則要么為空序列（別忘了這個）阻塑，要么的最后一項是, 且顯然有。無論是哪種情況我們都可以把接到這個后面,從而得到一個更長的公共子序列菠隆。矛盾！

  • 如果我們從序列中刪掉最后一項得到,從序列中也刪掉最后一項得到骇径，(多說一句角標為0時躯肌，認為子序列是空序列)，則我們從也刪掉最后一項得到的序列是破衔。為什么呢清女？和上面的道理相同，如果得到的序列不是晰筛，則它一定比短（注意是個集合！）读第，那么它后面接上元素t得到的子序列也比接上元素得到的子序列短曙博，這與是最長公共子序列矛盾。

  • 因此最后接上元素

  • 

  (2)

  • 仍然設, 或者是空序列（這時是未定義值不等于任何值）怜瞒。則和至少有一個成立父泳，因為不能同時等于兩個不同的值
    (2.1)
    如果，則有，因為根本沒的事嘛惠窄。
    
    (2.2)
    如果,類似
    
  • 我們事先并不知道逝她，由定義，我們取最大的一個睬捶，因此這種情況下,有

• 目前得到的有：
  
  (1)
  (2)

• 一個空序列和任何序列的最長公共子序列都是空序列
  
  (1)
  (2)
  (3)

for x = 0 to n do
    for y = 0 to m do
        if (x == 0 || y == 0) then 
            LCS(x, y) = 0
        else if (Ax == By) then
            LCS(x, y) =  LCS(x - 1,y - 1) + 1
        else 
            LCS(x, y) = ) max(LCS(x – 1, y) , LCS(x, y – 1))
        endif
    endfor
endfor

求最大公共子序列

• 的值來源的三種情況

  • （1）如果黔宛，這對應末尾接上

  • （2.1） 如果且
    這對應
    （2.2） 如果且
    這對應

  • （3） ，這對應

• 當時擒贸，其實走哪個分支都一樣臀晃，雖然長度時一樣的，但是可能對應不同的子序列介劫，所以最長公共子序列并不唯一

//用來記錄Xi和Yj的最長公共子序列的長度
private int[][] c;
//用來標識Xi和Yi的最長公共子序列是由哪種情況得來：c[i][j-1]徽惋、c[i-1][j]、c[i][j]+1座韵。 
//該數組能還原出最長公共子序列
private int[][] s;
void LCSLength(String a, String b){
   // x和y的最前端分別加上0
   char[] x = ("0"+a).toCharArray();
   char[] y = ("0"+b).toCharArray();

   c = new int[x.length][y.length];
   s = new int[x.length][y.length];

   // 初始化c险绘、s
   for( int i=0; i<x.length; i++ ){
       c[i][0] = 0;
   }
   for( int i=0; i<y.length; i++ ){
       c[0][i] = 0;
   }

   // 從上到下、從左到右填充c誉碴、s數組
   for( int i=1; i<x.length; i++ ){
       for( int j=1; j<y.length; j++ ){
           if( x[i]==y[j] ){
               c[i][j] = c[i-1][j-1]+1;
               s[i][j] = 1;
           }
           else if ( c[i-1][j] >= c[i][j-1] ){
               c[i][j] = c[i-1][j];
               s[i][j] = 2;
           }
           else {
               c[i][j] = c[i][j-1];
               s[i][j] = 3;
           }
       }
   }
}

//根據s數組求最大公共子序列
StringBuilder sb = new StringBuilder();

void CLCS( int i, int j ){
   if ( i==0 || j==0 ) return;
   if ( s[i][j]==1 ) {
       CLCS( i-1,j-1 );
       sb.append( x[i] ); // 為了讓公共子序列正序輸出宦棺，因此需要在遞歸調用之后將x[i]添加至sb
   }
   else if ( s[i][j]==2 ){
       CLCS( i-1,j );
   }
   else {
       CLCS( i,j-1 );
   }
}

原理和代碼總結來源于：

• 動態(tài)規(guī)劃法(三)——最長公共子序列
• 動態(tài)規(guī)劃基礎篇之最長公共子序列問題