最长公共子序列问题： 给定两个字符串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]);
}
}
网友评论