动态规划系列问题-最长公共子序列

2021年11月18日 5点热度 0条评论 来源: hellolittlebaby

最长公共子序列(Longest Common Subsequence, LCS)


题目描述:

给定两个字符串str1和str2,返回两个字符串的最长公共子序列的长度。

例如:str1="1A2C3D4B56" ,str2="B1D23CA4B6A",则"123456"和"12C4B6"都是最长公共子序列。

注意最长公共子序列与最长公共子串的区别,串要求是连续的,而序列不一定是连续的。

分析:

用一个二维数组来作动态规划表,假设str1长度为m,str2长度为n,则二维数组大小为dp[m][n];

dp[i][j]:表示str1[ 0.....i ]和str2[ 0......j ]的最长公共子序列的长度;

如何生成dp[][]:

<1>对于矩阵的第一行:
dp[0][j],即str1的第一个字符与str2的最长公共子序列。从前往后遍历str2,如果碰到与str1[0]相同的字符,则将对应的dp[0][j]置为1,一旦有dp[0][j]=1,则后面的dp[0][j+1.....n-1]全为1。

<2>对于矩阵的第一列:
dp[i][0],即str2的第一个字符与str1的最长公共子序列。
与第一行同理,一旦有dp[i][0]=1,则后面的dp[i+1.....m-1][0]全为1。

<3>对于一般的dp[i][j]:

其值只可能来自三种情况dp[i][j-1], dp[i-1][j], dp[i-1][j-1]+1(str1[i]和str2[j]表示的字符相同),取这三种情况中的最大值。

则str1和str2的最长公共子序列的长度为dp[m-1][n-1],时间复杂度为O(MN),空间复杂度为O(MN)。

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        if(A==null||n==0||B==null||m==0)
            return 0;
        char[] cha=A.toCharArray();
        char[] chb=B.toCharArray();
        int[][] dp=new int[n][m];
        dp[0][0]=cha[0]==chb[0]?1:0;
        //求dp第一行
        for(int i=1;i<m;++i){
            dp[0][i]=cha[0]==chb[i]?1:dp[0][i-1];
        }
        //求dp第一列
        for(int i=1;i<n;++i){
            dp[i][0]=chb[0]==cha[i]?1:dp[i-1][0];
        }
        for(int i=1;i<n;++i){
            for(int j=1;j<m;++j){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                if(cha[i]==chb[j])
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
            }
        }
        return dp[n-1][m-1];
    }
}

简便写法:

不用先求第一行和第二行,将dp大小设为(n+1)*(m+1),这样第一行和第一列就不用初始化了。

public class LCS {
    public static int getLenOfMaxCommonSeq(String str1, String str2){
        if(str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0)
            return 0;
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        for(int i = 1; i <= str1.length(); ++i){
            for(int j = 1; j <= str2.length(); ++j){
                
                if(str1.charAt(i-1) == str2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[str1.length()][str2.length()];
    }
}


通过dp[][]得到最长公共子序列:

1.从dp[m-1][n-1]开始向上移,移动的方向有向上,向左,向左上 三种;
2.如果dp[i][j]大于dp[i][j-1]或者dp[i-1][j],则表示在计算dp[i][j]的时候一定是选择了决策dp[i-1][j-1]+1,那么表明str1[i]=str2[j],则把str1[i]添加到子序列中,并向左上方移动;
3.如果dp[i][j]等于dp[i][j-1],则说明计算dp[i][j]的时候dp[i-1][j-1]+1不是必须选择的决策,直接向左移动
即可;
4.如果dp[i][j]等于dp[i-1][j] ,同理,直接向上移动;
5.如果dp[i][j]同时等于dp[i-1][j]和dp[i][j-1],随便选一个,反正不会错过必须选择的字符。
所以通过dp[][]求最长公共递增子序列的问题,就是还原求dp[][]的过程,时间复杂度为O(M+N)。

注:
如果只用求最长公共子序列长度,可以将空间复杂度压缩到O(MIN{M,N}),参照“矩阵的最小路径和”问题。

相关问题:

动态规划系列问题-最长公共子串:点击打开链接

    原文作者:hellolittlebaby
    原文地址: https://blog.csdn.net/u013328850/article/details/53187345
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。