共计 807 个字符，预计需要花费 3 分钟才能阅读完成。
最长公共子序列
动态规划问题，局部最小单元：两值是否相等，相等则从对角线上个位置处的数值 +1，继续状态延续；不相等则从上下两个过去的位置找值保持延续，在上下两个过去位置中保持着之前的最长子序列。
3. 对于状态的理解，保持最佳的，或者延续最佳的。
public class LongestCommonSubsequence {
public static int compute(char[] str1, char[] str2) {
int substringLength1 = str1.length;
int substringLength2 = str2.length;
int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
for (int i = substringLength1-1; i >= 0; i–) {
for (int j = substringLength2-1; j >= 0; j–) {
// System.out.println(i);
// System.out.println(j);
// System.out.println(“-*- “);
if (str1[i] == str2[j]) {
opt[i][j] = opt[i + 1][j + 1] + 1;
} else {
opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
}
}
}
return opt[0][0];
}
public static int compute(String str1,String str2){
return compute(str1.toCharArray(),str2.toCharArray());
}
public static void main(String[] args){
String a1=”abcd”;
String a2=”bcead”;
int l1=compute(a1,a2);
System.out.println(l1);
}
}
