Java算法:求两个字符串的最长公共子序列问题

最长公共子序列问题： 给定两个字符串A、B，求A与B的最长公共子序列（子序列不要求是连续的） 

举例： 

字符串A： abcdef 

字符串B：cd12334 

输出：cd

解题思路

这个问题是动态规划的问题，可以用动态规划表来进行求解

dp[i][j]:定义为a串第i位置b串第j位置以前的两个序列的最大的LCS，那么显而易见，dp[0][0]=0,dp[n][m]就是我们要求的最大值

状态转移方程：

1.a[i]=b[j]   dp[i][j]=dp[i-1][j-1]+1  

2.a[i]!=b[j]   dp[i][j]=max(dp[i-1][j],dp[i][j-1])

ps：当 i , j 位置的字符串相同的时候，我们i ，j 位置的值就是以前的LCS位置（i-1，j-1）加1

        当I ，j的字符串不相同时候，LCS的长度不会增加，但是我们有两种选择，就是i，j-1位置和i，j-1位置的值，我们选取最大的LCS作     为当前的LCS即可

动态规划

核心代码

for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

        if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;

        else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);

    }

}

代码