【動态規劃】最長公共子序列

最長公共子序列問題：

若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴格遞增下标序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應的遞增下标序列為{2，3，5，7}。

給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。

給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

蠻力法求解最長公共子序列：

需要周遊出所有的可能，時間複雜度是O(n³)，太慢了

動态規劃求解最長公共子序列：

分析規律：

設X=<x1,x2,x3,x4...,xm>，Y=<y1,y2,y3,y4...,yn>為兩個序列，Z=<z1,z2,z3,z4...,zk>是他們的任意公共子序列

經過分析，我們可以知道：

1、如果xm = yn，則zk = xm = yn 且 Zk-1是Xm-1和Yn-1的一個LCS

2、如果xm != yn 且 zk != xm，則Z是Xm-1和Y的一個LCS

3、如果xm != yn 且 zk != yn，則Z是X和Yn-1的一個LCS

是以如果用一個二維數組c表示字元串X和Y中對應的前i，前j個字元的LCS的長度話，可以得到以下遞歸公式：

是以，我們動态規劃就可以以自底向上的方式進行求解

隻需要從c[0][0]開始填表，填到c[m-1][n-1]，所得到的c[m-1][n-1]就是LCS的長度

int LCSLength(int m,int n,char *x,char *y,int **c,int **b) //c數組用來記錄子序列長度，b數組記錄具體的子序列，構造序列時                              可以用到！
  {
  
      for(int i=0;i<=m;i++){// //初始化第0行
  
          c[i][0]=0;
      }
      for(int j=0;j<=n;j++){// //初始化第0列
          c[0][j]=0;
     }
     for(int i=1;i<=m;i++) //填表
         for(int j=1;j<=n;j++){
             if(x[j]==y[i]){  
                 c[i][j]=c[i-1][j-1]+1;
                 b[i][j]=1;  //1:表示X[i]和y[j]的最長公共子序列是由x[i-1]和y[j-1]的最長公共子序列後面加上x[i]所得到的
             }else if(c[i-1][j]>=c[i][j-1]){
                c[i][j]=c[i-1][j];
                b[i][j]=2;//2:表示X[i]和y[j]的最長公共子序列與x[i-1]和y[j]的最長公共子序相同
              else{
                 c[i][j]=c[i][j-1];
                 b[i][j]=3;//3:表示X[i]和y[j]的最長公共子序列與x[i]和y[j-1]的最長公共子序相同
                }
             }
     }           

但是，我們怎麼得到LCS本身而非LCS的長度呢？

上面的b數組就派上了用場！b[i][j]記錄的是c[i][j]的值是由哪個子問題的解得到的，是以，從b[m][n]反向周遊數組即可得到具體的最長公共子序列！