1317 最长公共子序列 (LCS 线性DP)
题目描述
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。
例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
给定两个字符串，求他们的最长公共子序列。(字符串长度不超过2000)。
输入
输入两行，每行输入一个字符串，只包括小写字母。
输出
输出最长公共子序列长度。
样例输入
abcfbc
abfcab
样例输出
4
思路
最长公共子序列(LCS)：给定两个长度分别为N和M的字符串A和B，求即是A的子序列又是B的子序列的字符串长度最长是多少？
问题可以拓展，比如三个字符串的最长公共子序列。
状态表示：F[i][j]表示前缀字串A[1~i]与B[1~j]的“最长公共子序列”的长度
阶段划分：已经处理的前缀长度（两个字符串中的位置，即一个二维坐标）
转移方程：F[i][j]=max{F[i-1][j], F[i][j-1], F[i-1][j-1](A[i]==B[i])}
初始值：F[i][0]=F[0][j]=0
答案：F[N][M]
B站视频：
https://www.bilibili.com/video/BV1Mb4y1x7hu/
using namespace std;const int M=2005;char A[M],B[M];int F[M][M];int main(){scanf("%s",A+1);scanf("%s",B+1);int n=strlen(A+1), m=strlen(B+1);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(A[i]==B[j]) F[i][j]=F[i-1][j-1]+1;else F[i][j]=max(F[i-1][j], F[i][j-1]);printf("%d",F[n][m]);return 0;}