题目描述

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

输入格式

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

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

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

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

输出格式

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

思路

因为有两个字符串，所以状态表示需要为二维，f[i,j]表示以i结尾的字符串a和以j结尾的字符串b所构成的公共子序列的数量，所求即为MAX。其中状态计算需要分为四种情况，无i无j (f[i - 1, j - 1]), 无i有j (f[i - 1, j]), 有i无j (f[i,j -1]) 以及有i有j (f[i - 1, j - 1] + 1);
此处需要强调的两点：
1.无i有j 与 f[i - 1, j]并不是完全等价，因为f[i - 1, j]表示i - 1，j结尾的公共子序列数量，但不一定有a[i - 1] = b[j]，只是包含这种情况。由此可见，f[i - 1, j]与f[i, j - 1]会出现重合，但因为求的是最大值，所以不影响。
2.无i无j的情况被后者所包含，所以可以省略。由此则需比较，f[i - 1, j]，f[i, j - 1]以及(f[i - 1, j - 1] + 1) (当a[i] = b[j] 是才需要讨论有i有j)

时间复杂度

状态表示为二维 O(n^2), 而转移方程为三次运算，即为O(1)，二者相乘，即为 $O(n^2)$

JAVA 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int N = 1010;
        String a = sc.next();
        String b = sc.next();
        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][j - 1], f[i - 1][j]);
                if (a.charAt(i - 1) == b.charAt(j - 1)) { 
                //  此处要注意，因为状态转移方程有i - 1，j - 1所以将i，j从1开始，但对于字符串因为index是从0开始，则需要比较i - 1，而不是i
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}