题目描述

线性DP f(i,j)表示 A[1至i] 与 B[1至j] 的公共子序列的集合
10 表示 包含a[i]但不包含b[j] 以此类推

样例

import java.util.*;

/*
  00，10，01，11
  00状态是包含于10和01  所以00状态是不用管的

  对于11状态 a[i]应该等于b[i]
*/

public class Main {
    static int N = 1010;
    static int n;
    static int m;
    static char[] a = new char[N];
    static char[] b = new char[N];
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 读取输入字符串
        String inputA = scanner.next();
        String inputB = scanner.next();
        for (int i = 0; i < n; i++) {
            a[i + 1] = inputA.charAt(i);
        }
        for (int i = 0; i < m; i++) {
            b[i + 1] = inputB.charAt(i);
        }

        // 动态规划求解
        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]) {//包含a[i] 和 b[j] 其实就是它们相等
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }

        // 输出结果
        System.out.println(f[n][m]);
    }
}