最长公共子序列

题目描述：

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

输入：

第一行输入序列X，第二行输入序列Y。

输出：

X和Y的最长公共子序列的长度。

样例输入

abcbdab
bdcaba

样例输出

4

思路：

代码：

#include <iostream>
#include <string.h>
#include <math.h>
 
using namespace std;
 
int main() {
    int c[201][201];
    memset(c,0,sizeof(c));
    int i, j;
    string x, y;
    cin >> x >> y;
    x = " " + x;        //使得字符串x、y从1开始
    y = " " + y;
    int m = x.length(), n = y.length();
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (x[i] == y[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;      //c[i][j] = c[i-1][j-1]
            } else
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);    //c[i][j] = max(c[i-1)[j],c[i][j-1]
        }
    }
    cout << c[m-1][n-1];
    return 0;
}