51nod--1006 最长公共子序列Lcs （动态规划）

题目：

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A

第2行：字符串B

(A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Input示例

abcicba

abdkscab

Output示例

abca

分析：

这次要打印LCS， 所以需要额外的处理；

一般LCS ， 我们知道 Dp[i][j] 的值只会来自 Dp[i-1][j], Dp[i][j-1], Dp[i-1][j-1];

而我们知道， 当 Dp[i][j] == Dp[i-1][j-1] 时， 就是两个字符相等的时候。

所以我们只需要从 Dp[n][m] 回溯就好了

实现：

#include <bits/stdc++.h>

using namespace std;

const int maxn  = 1000 + 131;

char s[maxn], t[maxn];

int Dp[maxn][maxn];

void Solve() {

    // Dp 部分

    int n = strlen(s),

        m = strlen(t);

    memset(Dp, 0, sizeof(Dp));

    for(int i = 0; i < n; ++i)

        for(int j = 0; j < m; ++j) {

            if(s[i] == t[j])

                Dp[i+1][j+1] = Dp[i][j] + 1;

            else

                Dp[i+1][j+1] = max(Dp[i][j+1], Dp[i+1][j]);

        }

    // 回溯部分

    int i = n, j = m;

    stack<char> Ans;

    while(Dp[i][j]) {

        if       (Dp[i][j] == Dp[i-1][j]) i--;

        else if  (Dp[i][j] == Dp[i][j-1]) j--;

        else     Ans.push(s[i-1]), i--, j--;

    }

    while(Ans.empty() == false) {

        cout << Ans.top();

        Ans.pop();

    }

}

int main() {

    while(cin >> s >> t) {

        Solve();

    }

    return 0;

}