最长公共子序列（LCS）

1. 描述：

给定两个字符串（或数字序列）A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）。

2. 例子：

如字符串“sadstory” 和 “adminsorry”的最长公共子序列为“adsory”，长度为6。

3. 动态规划解法：

设字符串A，B的长度分别为n，m。

1）令dp[i][j] 表示字符串A的 i 号位和字符串B的 j 号位之前的LCS的长度（下标从1开始）。如dp[4][5]表示“sads”与“admin”的LCS长度。

2）若A[i] == B[j]，则字符串A与字符串B的LCS增加了1位，即dp[i][j] = dp[i-1][j-1] +1。

3）若A[i] != B[j]，则字符串A的i号位和字符串B的j号位之前的LCS无法延长，因此dp[i][j] 将会继承dp[i-1][j] 与 dp[i][j-1]中的较大值，即有dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。

4）可以得到状态转移方程：

• 　　dp[i][j] = dp[i-1][j-1] +1 　　                  A[i] == B[j]
• 　　dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }        A[i] != B[j]
• 　　边界：dp[i][0] == dp[0][j] ==0   （0≤i≤n，0≤j≤m）

5）时间复杂度为O(mn)。

#include<cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
char A[N], B[N];
int dp[N][N];
int main(){
    int n;
    gets(A+1);  //从下标为1开始读人
    gets(B+1);
    int lenA = strlen(A+1); //读取长度也相应的从+1开始
    int lenB = strlen(B+1);
    //边界
    for (int i=0; i<=lenA; i++) {
        dp[i][0] = 0;
    }
    for (int j=0; j<=lenB; j++) {
        dp[0][j] = 0;
    }
    //状态转移方程
    for (int i=1; i<=lenA; i++) {
        for (int j=1; j<=lenB; j++) {
            if (A[i]==B[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    printf("%d
",dp[lenA][lenB]);   //dp[lenA][lenB] 是答案
    return 0;
}

 4. 注意：

代码中边界和状态转移方程的循环终止条件都是小于等于字符串的长度。