题目描述

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

输入格式
第一行包含两个整数N和M。

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

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

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

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

数据范围
1≤N,M≤1000

样例

输入样例:

4 5
acbd
abedc

输出样例：

3

算法

DP $O(n^2)$

谈一下自己的理解：
f[i][j]是字符串q的前i个字符和字符串p的前j个字符中公共子序列的最大值。
计算f[i][j]的时候将其划分为4种情况:q[i]p[i]都不取，q[i]取p[j]不取，q[i]不取p[i]取，q[i]p[i]都取。
都取的情况q[i]==p[i]，q[i]p[i]都不取对应f[i-1][j-1]
剩下两种情况用f[][]形式不好表示但是其被包含在f[i-1][j]和f[i][j-1]中。
这两种状态包含的情况是大于上述情况的且存在并集，但是取值为最大值不影响。

时间复杂度

Java 代码

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();int m = sc.nextInt();
        String p = " " + sc.next(), q = " " + sc.next();
        int[][] f = new int[n + 1][m + 1];

        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(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
            }
        }
        System.out.println(f[n][m]);
    }
}