dp 最長公共子序列

題目：

給兩個字元串， str1， str2；

列印出最長公共子序列；

如：

abbbbv

vbbbba

答案是：

bbbb（答案不唯一）

了解：

以前學過一下，寫的出來那種算長度的題目；

但這種求最終序列的題确實沒做過；

然後就很傻的開了一個10的9次方的空間來做，發現直接爆了；

最後看了解題過程才過的；

最長公共子序列：

根據推測可知：

如果str1[i] != str2[j]；

則：目前長度與前面求出的最大長度相等；

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])；

如果相等；

則：目前長度為前一個的長度加 1；

即：dp[i][j] = dp[i - 1][j - 1] + 1；

而在推導出 dp 數組後會發現；

我們向前推回去就可以找到一個字元串；

這個字元串便是結果中的一種；

那麼怎麼推回去呢？

在前面推導的基礎上，我們可以發現；

相等的時候是加了一個 1；

則說明我們該在答案裡加入相應的值；

而不相等的時候，我們是取的最大值；

那麼，回退的時候我們就應該向值大的方向退；

代碼如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const double MIN_INF = ;
const int MAX_INF = () + ;

#define X first
#define Y second

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    vector<vector<int> > dp(str1.length() + , vector<int>(str2.length() + , ));
    for (int i = ; i <= str1.length(); ++i) {
        for (int j = ; j <= str2.length(); ++j) {
            if (str1[i - ] == str2[j - ]) {
                dp[i][j] = dp[i - ][j - ] + ;
            }
            else {
                dp[i][j] = max(dp[i - ][j], dp[i][j - ]);
            }
        }
    }
    string ans = "";
    for (int i = str1.length(), j = str2.length(); i >=  && j >= ;) {
        if (str1[i - ] == str2[j - ]) {
            ans += str1[i - ];
            --i, --j;
        }
        else {
            if (dp[i - ][j] >= dp[i][j - ]) {
                --i;
            }
            else {
                --j;
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    return ;
}