什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。
举个例子，如：有两条随机序列，如 1 3 4 5 5and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。
Xi=﹤x1，?，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀）
Yj=﹤y1，?，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀）。
若xm=yn（最后一个字符相同），则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时，问题化归成求Xm-1与Yn-1的LCS（LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1）。
若xm≠yn，则亦不难用反证法证明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立，若zk≠xm则有Z∈LCS(Xm-1 , Y)，类似的，若zk≠yn 则有Z∈LCS(X , Yn-1)。此时，问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为：max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。
由于上述当xm≠yn的情况中，求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度，这两个问题不是相互独立的：两者都需要求LCS(Xm-1，Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质考虑用动态规划法。
//伪代码 L(A,B,L){//字符串A，B，所求矩阵L for(k=1;k<=m;k++){ //m 为A 的长度 for(i=1;i<=m;i++){ if(i<k) L[k][i]=N;//i<k 时,L(k,i)=null，N 代表无穷大 if(L[k][i]==k)//L(k,i)=k 时,L(k,i+1)=L(k,i+2)=…L(k,m)=k for(l=i+1;l<=m;l++) { L[k][l]=k; Break;} for(j=1;j<=n;j++){//定理4 的实现 if(A[i+1]==B[j]&&j>L[k-1][i]){ L[k][i+1]=(j<L[k][i]?j:L[k][i]); break; } if(L[k][i+1]==0) L[k][i]=N; } if(L[k][m]==N) {p=k-1;break;} } p=k-1; }
代码
#include<iostream> using namespace std; int dp[1001][1001],a1[2001],a2[2001],n,m; int main() { //dp[i][j]表示两个串从头开始，直到第一个串的第i位 //和第二个串的第j位最多有多少个公共子元素 cin>>n>>m; for(int i=1; i<=n; i++)cin>>a1[i],dp[i][0]=0; for(int i=1; i<=m; i++)cin>>a2[i],dp[0][i]=0; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(a1[i]==a2[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); //因为更新，所以++; } } cout<<dp[n][m]; }
原文：https://www.cnblogs.com/zhhhb/p/12972553.html