转载

最长公共子序列

最长公共子序列

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

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

  • 最优子结构

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

    原问题: X = ( x 1 , x 2 , x 3 , . . . x m ) X=(x_1, x_2, x_3,...x_m) , Y = ( y 1 , y 2 , y 3 . . . y n ) Y=(y_1, y_2, y_3...y_n) 是两个序列,求最长的

    Z = ( z 1 , z 2 , z 3 , . . . z k ) Z=(z_1, z_2, z_3,...z_k) 使得 Z Z 同时是 X , Y X,Y 的子序列

    假设 Z = ( z 1 , z 2 , z 3 , . . . z k ) Z=(z_1, z_2, z_3,...z_k) 是原问题的最优解,则以下成立

    • 如果 x 1 = = y 1 x_1==y_1 ,则 ( z 2 , z 3 , z 4 , . . . z k ) (z_2, z_3, z_4,...z_k) 是子问题求 ( x 2 , x 3 , . . x m ) (x_2,x_3,..x_m) ( y 2 , y 3 , . . . y n ) (y_2,y_3,...y_n)

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

    • 如果 x 1 ! = y 1 x_1!=y_1 ,则 ( z 1 , z 2 , . . . z k ) (z_1,z_2,...z_k) 是子问题求 ( x 1 , x 2 , . . . x m ) (x_1, x_2,...x_m) ( y 2 , y 3 , . . y n ) (y_2,y_3,..y_n)

      最长公共子序列的最优解,或者是子问题求 ( x 2 , x 3 , . . . x m ) (x_2,x_3,...x_m) ( y 1 , y 2 , y 3 , . . y n ) (y_1,y_2,y_3,..y_n) 的最

      长公共子序列的最优解

    证明

    • 如果 ( z 1 , z 2 , z 3 , . . z 4 ) (z_1,z_2,z_3,..z_4) 不是子问题的最优解,则存在比其更长的公共子序列是子问题的

      最优解,在这种情况下原问题的最优解得长度就会大于 ( z 1 , z 2 , z 3 . . . z n ) (z_1, z_2, z_3...z_n) ,与假设矛盾

      或者的情况证明类似

  • 子问题重叠

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

    一下公式:
    F ( m , n ) = { 0     m = 0   o r   n = 0 F ( m ? 1 , n ? 1 ) + 1     x m = = y n    ( m > 0   a n d   n > 0 ) m a x ( F ( m , n ? 1 ) , F ( m ? 1 , n ) )     x m ! = y n   ( m > 0   a n d   n > 0 ) F(m,n)=\left\{ \begin{aligned} 0 \ \ \ 若m=0 \ or \ n =0 \\ F(m-1, n-1)+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.
    从公式可以看出,求解原问题的时候回重复计算某些子问题

  • 实例 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();
        }
        }
    }
    
正文到此结束
本文目录