蓝桥杯javaC组——算法提高【最长公共子序列】

【ADV-317 最长公共子序列】

地址：“蓝桥杯”练习系统

问题描述

　　给定两个字符串，寻找这两个字串之间的最长公共子序列。

输入格式

　　输入两行，分别包含一个字符串，仅含有小写字母。

输出格式

　　最长公共子序列的长度。

样例输入

abcdgh
aedfhb

样例输出

3

样例说明

　　最长公共子序列为a，d，h。

数据规模和约定

　　字串长度1~1000。

解题思路
两个字符串动态查找即可

【注意·要点】

1.序列和数列的区别：数列的排列是连续且顺序固定的，而序列是可以不连续但是次序不能更改的。

2. dp循环的判断条件注意是动态继承，即继承是字符串的长度不断从小再到大，这也是dp能抽象解决问题的特点

【代码】

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        sc.close();
        //dp状态数组
        int dp[][] = new int[a.length()+1][b.length()+1];//0行和0列 为0
        //循环查找公共子序列
        for (int i = 1; i < dp.length; i++) {//字符串a
            for (int j = 1; j < dp[0].length; j++) {//字符串b
                if(a.charAt(i-1) == b.charAt(j-1)) 
                    dp[i][j] = dp[i-1][j-1]+1;    ///公共子序列长度+1
                else 
                    //继承两个字符串当前长度的最大公共子序列
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); 
            }
        }
        System.out.println(dp[a.length()][b.length()]);
    }
 
}
动态规划经典