最长公共子序列

最长公共子序列

最长公共子序列是经典的动态规划问题，下面从动态规划的两个重要特征，最优子结构和

子问题重叠来分析问题，同时要保证子问题的完整性。

• 最优子结构

  最优子结构的意思就是原问题的最优解中包含子问题的最优解

  原问题:$X=(x_1, x_2, x_3,...x_m)$X=(x1​,x2​,x3​,...xm​), $Y=(y_1, y_2, y_3...y_n)$Y=(y1​,y2​,y3​...yn​)是两个序列,求最长的

  $Z=(z_1, z_2, z_3,...z_k)$Z=(z1​,z2​,z3​,...zk​)使得$Z$Z同时是$X,Y$X,Y的子序列

  假设$Z=(z_1, z_2, z_3,...z_k)$Z=(z1​,z2​,z3​,...zk​)是原问题的最优解，则以下成立

  • 如果$x_1==y_1$x1​==y1​,则$(z_2, z_3, z_4,...z_k)$(z2​,z3​,z4​,...zk​)是子问题求$(x_2,x_3,..x_m)$(x2​,x3​,..xm​)和$(y_2,y_3,...y_n)$(y2​,y3​,...yn​)

    的最长公共子序列的最优解

  • 如果$x_1!=y_1$x1​!=y1​,则$(z_1,z_2,...z_k)$(z1​,z2​,...zk​)是子问题求$(x_1, x_2,...x_m)$(x1​,x2​,...xm​)和$(y_2,y_3,..y_n)$(y2​,y3​,..yn​)的

    最长公共子序列的最优解，或者是子问题求$(x_2,x_3,...x_m)$(x2​,x3​,...xm​)和$(y_1,y_2,y_3,..y_n)$(y1​,y2​,y3​,..yn​)的最

    长公共子序列的最优解

  证明

  • 如果$(z_2, z_3, z_4,...z_k)$(z2​,z3​,z4​,...zk​)不是子问题的最优解，则存在比其更长的公共子序列是子问题

    的最优解，则原问题存在比$(z_1, z_2, z_3...z_n)$(z1​,z2​,z3​...zn​)更长的最优解，与假设矛盾，故不成立

  • 如果$(z_1,z_2,z_3,..z_4)$(z1​,z2​,z3​,..z4​)不是子问题的最优解，则存在比其更长的公共子序列是子问题的

    最优解，在这种情况下原问题的最优解得长度就会大于$(x_1, x_2, x_3...x_n)$(x1​,x2​,x3​...xn​),与假设矛盾

    或者的情况证明类似

• 子问题重叠

  假设$F(m,n)$F(m,n)是长度分别为m和n的序列$X,Y$X,Y的最大公共子序列的长度,则由上面可以得到

  一下公式：
  $F(m,n)=\left\{ \begin{aligned} 0 \ \ \ 若m=0 \ or \ n =0 \\ F(m-1, n-1) \ \ \ 若x_m==y_n\ \ (m>0 \ and \ n > 0) \\ max(F(m,n-1), F(m-1, n)) \ \ \ 若x_m!=y_n \ (m>0 \ and \ n >0) \end{aligned} \right.$F(m,n)=⎩⎪⎨⎪⎧​0   若m=0 or n=0F(m−1,n−1)   若xm​==yn​  (m>0 and n>0)max(F(m,n−1),F(m−1,n))   若xm​!=yn​ (m>0 and n>0)​
  从公式可以看出，求解原问题的时候回重复计算某些子问题

• 实例 POJ1458

  AC代码

  import java.util.Scanner;
  import java.io.File;
  import java.io.FileNotFoundException;
  
  public class Main{
      public static void main(String args[]) {
          try{
          Scanner scanner = new Scanner(System.in);
          int arr[][] = new int[1000][1000];
          while(scanner.hasNext()) {
              String X = scanner.next();
              
              String Y = scanner.next();
  
              int m = X.length(); int n = Y.length();
  
              for(int i = 0; i <= m; i++)
                  for(int j = 0; j <= n; j++)
                      arr[i][j] = 0;
  
              for(int i = 1; i <= m; i++)
                  for(int j = 1; j <= n; j++) {
                      if(X.charAt(i-1) == Y.charAt(j-1)) {
                          arr[i][j] = arr[i-1][j-1] + 1;
                      }else{
                          arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
                      }
                  }
              System.out.println(arr[m][n]);
          }
      }catch(Exception e) {
          e.printStackTrace();
      }
      }
  }