[Java] 蓝桥杯ADV-202 算法提高最长公共子序列

问题描述
给定两个字符串，寻找这两个字串之间的最长公共子序列。
输入格式
输入两行，分别包含一个字符串，仅含有小写字母。
输出格式
最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
样例说明
最长公共子序列为a，d，h。
数据规模和约定
字串长度1~1000。

package adv202;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] a = ("," + in.nextLine()).toCharArray();
        char[] b = ("." + in.nextLine()).toCharArray();
        in.close();

        int[][] dp = new int[a.length][b.length];
        for (int i = 1; i < a.length; i++) {
            for (int j = 1; j < b.length; j++) {
                if (a[i] == b[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Integer.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        
        System.out.println(dp[a.length - 1][b.length - 1]);
    }

}

package adv202;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

char[] a = ("," + in.nextLine()).toCharArray();

char[] b = ("." + in.nextLine()).toCharArray();

in.close();

int[][] dp = new int[a.length][b.length];

for (int i = 1; i < a.length; i++) {

for (int j = 1; j < b.length; j++) {

if (a[i] == b[j]) {

dp[i][j] = dp[i - 1][j - 1] + 1;

} else {

dp[i][j] = Integer.max(dp[i][j - 1], dp[i - 1][j]);

}

System.out.println(dp[a.length - 1][b.length - 1]);

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版