最长公共子序列
我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度。
输入例子:
abcfbc abfcab
programming contest
abcd mnp
输出例子:
4
2
0
package com.tonyluis.oj;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str1 = in.next();
String str2 = in.next();
System.out.println(getLongestCommonSequence(str1, str2));
}
}
private static int getLongestCommonSequence(String A, String B) {
int res = Integer.MIN_VALUE;
int[][] dp = new int[A.length() + 1][B.length() + 1];
for (int i = 1; i <= A.length(); i++)
for (int j = 1; j <= B.length(); j++)
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
res = Math.max(res, dp[i][j]);
} else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
return res;
}
}