定义

最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。

接下来我们分析算法的状态转移方程
dp[i, j]代表a字符串前i个字符组成的子串和b字符串前j个字符组成的子串的LCS。 
那么 

根据上面的状态转移方程可以写出一下代码

for(int i = 1; i <= lena; ++i) {  
    for (int j = 1; j <= lenb; ++j) {  
        if(a[i - 1] == b[j - 1]) {  
            dp[i][j] = dp[i - 1][j - 1] + 1;  
        } else {  
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);  
        }  
    }  
}  

Coincidence
题目描述：
Find a longest common subsequence of two strings.
输入描述：
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
输出描述：
For each case, output k – the length of a longest common subsequence in one line.
输入样例#:
abcd
cxbydz
输出样例#:
2
题目来源：
DreamJudge 1293

题目解析：最长公共子序列（LCS）模板题。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
int dp[101][101];  
int main() {  
    string a, b;  
    memset(dp, 0, sizeof(dp));  
    cin >> a >> b;  
    int lena = a.size();  
    int lenb = b.size();  
    fo...

掌握最长公共子序列（LCS）