11579: 【原1579】LCS

题目

题目描述

author: ZH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1579 # Description 给出两个序列x[1..m]和y[1..n]，找出二者的一个最长公共子序列。一个子序列是原序列删除一些元素后得到的，剩下的元素必须保持相对顺序。例如x = ABCBDAB，y = BDCABA，则一个最长公共子序列为LCS(x, y) = BCBA。这里LCS借用函数记号来表示一个最长公共子序列。

Input Format

第一行有两个整数n,m ，分别代表序列x和y的长度。

接下来一行 n 个字母代表x序列。

接下来一行 m 个字母代表y序列。

Output Format

输出LCS（x,y）的长度

注意：答案没有对任何数取模。

Sample Input

7 6
ABCBDAB
BDCABA

Sample Output

4

Limits

对于100%的数据，1 <= n,m <= 1000。

ligongzzz's solution

#include "iostream"
#include "algorithm"
#include "cstring"
using namespace std;

int ansData[1000][1000];
char str1[1009], str2[1009];
int lcs(int start1, int start2, int end1, int end2) {
    if (start1 >= end1 || start2 >= end2) return 0;
    //判断是否重复
    if (ansData[start1][start2] >= 0) return ansData[start1][start2];
    //递归
    if (str1[start1] == str2[start2]) {
        ansData[start1][start2] = lcs(start1 + 1, start2 + 1, end1, end2) + 1;
        return ansData[start1][start2];
    }
    else {
        ansData[start1][start2] = max(lcs(start1 + 1, start2, end1, end2),
            lcs(start1, start2 + 1, end1, end2));
        return ansData[start1][start2];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int len1, len2;
    memset(ansData, -1, sizeof(ansData));

    cin >> len1 >> len2;
    cin >> str1 >> str2;

    cout << lcs(0, 0, len1, len2);

    return 0;
}

Neight99's solution

#include <cmath>
#include <iostream>

using namespace std;

const int maxN = 1e3 + 100;

int n, m, dp[maxN][maxN] = {0};
char N[maxN] = {0}, M[maxN] = {0};

int DP(int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int ans;
    cin >> n >> m >> N >> M;
    ans = DP(n - 1, m - 1);

    cout << ans;
    return 0;
}

int DP(int x, int y) {
    if (x < 0 || y < 0) {
        return 0;
    } else if (dp[x][y] != 0) {
        return dp[x][y];
    } else if (N[x] == M[y]) {
        dp[x][y] = DP(x - 1, y - 1) + 1;
    } else {
        dp[x][y] = max(DP(x - 1, y), DP(x, y - 1));
    }

    return dp[x][y];
}

WashSwang's solution

#include <iostream>
using namespace std;
int n,m,dp[1005][1005];
char x[1005],y[1005];
int main() {

    cin>>n>>m;
    cin>>x>>y;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        {
            if (x[i-1]==y[j-1])
                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];
    return 0;
}

yyong119's solution

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 1005;
char a[MAX_N], b[MAX_N];
int n, m;
int f[MAX_N][MAX_N];

int main() {

    cin >> n >> m;
    cin >> a; cin >> b;
    for (int i = n; i > 0; --i) a[i] = a[i - 1];
    for (int i = m; i > 0; --i) b[i] = b[i - 1];
    a[0] = b[0] = '*';
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    cout << f[n][m] << endl;
    return 0;
}