【DP入门】最长公共子序列

题目来自nyist第36题，如下： 描述 咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0<N<100)表示待测数据组数 接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000. 输出 每组测试数据输出一 个整数，表示最长公共子序列长度。每组结果占一行。 本题在算法导论上有详细的方法求出最长子序列以及其长度，其代码网上有许多，大致可以概括为下图（摘自算法导论）。 由于本题不需要求出子序列值，所以可以进行一定程度的化简以及优化。 既然只需要求出长度，即图中最后一行，故可以用全局变量进行记录，将二维数组化简为一维数组（算法导论的练习题中有提到）。 思路是将一个序列固定，比如将上图中yi序列固定不变，xi从1-m增加，即先考虑A，再考虑AB，再考虑ABC......（每次仅需要对新加入的字符进行计算）。计算方法是先判断x[i]与y[j]是否相等，相等则（dp[i] = 上一组dp中的dp[i-1]+1），否则判断当前dp[i]是否比dp[i-1]小，如果是，则dp[i] = dp[i-1]，否则（dp[i]=上一组的dp[i]）。dp数组在这里指y序列前i个值与x序列的LCS，随着x序列的增长不断更新整个dp数组。问题在与怎么保存上一组的dp[i-1]，因为计算当前组的dp[i]时是已经计算完当前组的dp[i-1]的，即dp数组前i-1个值已经更新了，所以这里需要用全局变量来维护，且仅需要维护上一组的dp[i-1]这一个值。具体维护方法见代码中olddp和t。 代码如下： #include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[1000+5]; char s1[1000+5],s2[1000+5]; int main() { int N,n,i,j,olddp,t; cin>>N; while(N--) { memset(dp,0,sizeof(dp)); scanf("%s",s1); scanf("%s",s2); for(i = 0;s2[i] != '\0';i++) { olddp=0; for(j = 0;s1[j] != '\0';j++) { t=dp[j]; if(s1[j]==s2[i]) dp[j]=olddp+1; else if(dp[j]<dp[j-1]) dp[j]=dp[j-1]; olddp=t; } } cout<<dp[j-1]<<endl; } return 0; } 这里j = x序列的长度，故dp[j-1]的值即为x序列与y序列的LCS的长度。可能dp[j-3] = dp[j-2] = dp[j-1]，但是dp数组的最后一个值一定为最大值。