题目描述

给你一个序列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()];
    }
}