最长公共子序列

链接：https://www.acwing.com/problem/content/898/

来源：ACWing 算法基础课

题目描述

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

1
2
3
4 5
acbd
abedc

输出样例：

1
3

算法描述

状态表示

本题使用二维数组dp来分别描述a，b两个char数组，在相应长度下的最长公共字符长度。

集合划分

以b[j]为结尾基准，可以这么理解——在i长度下，与b[j]的最大公共长度。

  1. 让dp[i] [j]=dp[i-1] [j]，应为i长度下肯定能包含i-1长度下的最大公共值
  2. 判断更新dp[i] [j] = max(dp[i] [j-1]，dp[i-1] [j]),因为在前面的1~j更新范围时，dp[i] [j-1]的值很有可能发生变化
  3. 进行了前面的两步操作，当a[i] = b[j]时，我们就可以让dp[i] [j]直接与dp[i-1] [j-1]+1进行比较，因为后者是直接还没有a[i]和b[j]的状态下获得的长度，找到了一样的加一，但由于底二步的的更新，则需要对两者进行比较。
  4. 在上述过程进行完成之后，我么就得到了最长公共子序列的值了

笔者代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 1010;
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String A = scanner.next();
        String B = scanner.next();
        char[] a = new char[N];
        char[] b = new char[N];
        for(int i=1; i<=n; i++){
            a[i] = A.charAt(i-1);
        }
        for(int i=1; i<=m; i++){
            b[i] = B.charAt(i-1);
        }
        int[][] f = new int[N][N];

        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= m ; j++) {
                f[i][j] = Math.max(f[i-1][j],f[i][j-1]);
                if(a[i] == b[j]){
                    f[i][j] = Math.max(f[i][j],f[i-1][j-1]+1);
                }
            }
        }

        System.out.println(f[n][m]);
    }
}