Acwing 897. 最长公共子序列 (每日一题）
最长公共子序列
题目描述
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
状态表示：
集合：所有从A[1,i] B[1,j]的公共子序列的集合
属性：max
像最长上升子序列，状态的划分依据是找不同的点。最长上升子序列确定以a[i]为结尾的子序列，共同点便是以a[i]作为结尾。划分依据：a[1,i-1]中的每个数作为最后一个不同点进行划分**
有没有发现：
DP基操：
1.找不同和相同之处/不同和固定之处
2.结合定义出发！
最长公共子序列的不同点在于i,j在不在序列中，可以将集合划分为4类。
实际上只有3类，且往下看。
(1)i、j 均不在
i、j均不包含其中，那只能从a[i-1]、b[j-1]中去选
得到如下状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j-1] f[i][j]=f[i−1][j−1]
(2)i不在，j在
i不在序列中，只能从前i-1中选，j可在可不在。
刚好i不在，j在，包含在这种情况中，且最大值/最小值是可以允许重复的。
得到如下状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]
(3)i在，j不在
j不在序列中，那j只能从j-1中选择。i可在可不在。
刚好**i在，j**不在，包含在这种情况中，且最大值/最小值是可以允许重复的。
得到如下状态转移方程:
f [ i ] [ j ] = f [ i ] [ j − 1 ] f[i][j]=f[i][j-1] f[i][j]=f[i][j−1]
(4)i、j均在
只有满足**a[i]==b[j]这一条件才存在。
确定了**a[i]、b[j]之后，剩下的从i-1、j-1中选出最长公共子序列，从定义出发，恰好就是f[i-1][j-1]中选。最后再加上固定好的a[i]、b[j]这一对即可。
得到如下状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 f[i][j]=f[i-1][j-1]+1 f[i][j]=f[i−1][j−1]+1
最后，(1)是既可以包含在(2)也可以包含在(3)中的，允许最值重复。重复没关系，求出的必定是最值且包含在整个集合中，是合法的。最后，总共只有3种情况。
求和/求值则不允许重复！！！
Accode
import java.util.*;
public class Main{static int N=1010;static int f[][]=new int[N][N];public static void main(String []args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();char a[]=(" "+sc.next()).toCharArray();char b[]=(" "+sc.next()).toCharArray();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//情况1包含在情况2、3中//情况2、3取一个maxf[i][j]=Math.max(f[i-1][j],f[i][j-1]);//满足a[i]==b[j]这一条件//再与情况4取一个maxif(a[i]==b[j])f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);}}//输出集合定义System.out.println(f[n][m]); }
}