题目描述

给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=是序列X=的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6>。
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？

输入描述

输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。

输出描述

对于每组输入，输出两个字符串的最长公共子序列的长度。

输入示例

abcfbc abfcab
programming contest 
abcd mnp

输出示例

4
2
0

 

 参考答案：（二维dp来解决）

import java.util.Scanner; // 导入Scanner类，用于从标准输入读取数据public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in); // 创建Scanner对象，用于读取标准输入while (in.hasNext()) { // 当标准输入还有下一行时，进入循环String s = in.nextLine(); // 读取下一行输入，并存储在字符串s中String[] s1 = s.split(" "); // 将字符串s以空格分割成字符串数组s1，s1[0], s1[1]代表两个字符串System.out.println(longestCommonSubsequence(s1[0], s1[1])); // 调用函数，并打印结果}}// 计算最长公共子序列的函数private static int longestCommonSubsequence(String s1, String s2) {// 创建一个二维数组dp来保存子问题的解，dp[i][j]表示s1前i个字符和s2前j个字符的最长公共子序列的长度int[][] dp = new int[s1.length() + 1][s2.length() + 1];// 将s1和s2转换为字符数组char[] chars1 = s1.toCharArray();char[] chars2 = s2.toCharArray();// 使用动态规划求解最长公共子序列的长度for (int i = 0; i < chars1.length; i++) {for (int j = 0; j < chars2.length; j++) {if (chars1[i] == chars2[j]) { // 如果当前字符相等dp[i + 1][j + 1] = dp[i][j] + 1; // 则当前位置的最长公共子序列长度为左上角元素加1} else { // 如果当前字符不相等// 则当前位置的最长公共子序列长度为上方或左方元素中的较大值dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);}}}// 返回s1和s2的最长公共子序列长度，即dp数组右下角元素的值return dp[s1.length()][s2.length()];}
}