漫画：最长公共子序列
关注“脚本之家”，与百万开发者在一起
-
当两个字符串 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);
}
}
推荐阅读：
每日打卡赢积分兑换书籍入口
👇🏻👇🏻👇🏻