漫画：最长公共子序列
时间：2020-10-09 21:13:23
手机看文章
扫描二维码
随时随地手机看文章
[导读]题目： 给定两个字符串 str1 和 str2，返回这两个字符串的最长公共子序列的长度。解释：一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
-
当两个字符串 i，j 索引对应的字符相等时，如下图示
此时 dp[i][j] 值可能为 dp[i-1][j] 或 dp[i][j-1]， dp[i-1][j] 怎么理解，既然 i 与 j 指向的字符不等，那只要丢弃 i 字符，求 str1[0..i-1] 与 str2[0..j] 的最长公共子序列即可，即 dp[i-1][j], 同理对于dp[i][j-1]，即为丢弃 j ，求 str1[0..i] 与 str2[0..j-1] 的最长公共子序列
既然 dp[i][j] 有可能等于这两个值，那么显然应该取这两者的较大值，
即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。综上可知状态状态方程如下：
阿宝的想法:
空字符串与任何字符串的最长公共子序列都为 0，所以 dp[0][i], dp[j][0] 都为 0（i
为 0 到 str1 的长度， j 为 0 到 str2 的长度）,如下图蓝色部分即为 base case。
代码如下
public class Solution {
public static int getLCS(char[] x, char[] y) {
// base case，以下 dp 中的每个元素默认值都为 0。
int dp[][] = new int[x.length][y.length];
for (int i = 1; i < x.length; i++) {
for (int j = 1; j < y.length; j++) {
// 以下逻辑为状态转移方程
if (x[i] == y[j]) {
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[x.length-1][y.length-1];
}
public static void main(String[] args) {
char[] x = {' ', 'a', 'b', 'c', 'e', 'f', 'g'};
char[] y = {' ', 'a', 'c', 'd', 'g'};
int lcs = getLCS(x, y);
System.out.printf("lcs = " + lcs);
}
}
特别推荐一个分享架构+算法的优质内容，还没关注的小伙伴，可以长按关注一下：
长按订阅更多精彩▼
如有收获，点个在看，诚挚感谢
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
下载文档
