（2011复旦机试） 最长公共子序列

题目类型：动态规划、最长公共子序列

问题描述：输入3个子串， 输出这3个子串的最大公共子串

• 输入：
• abcd acb abc
• 输出：
• ab

思路分析：

本体需要输出的不是最长公共子序列的长度或者和，本题要输出最长公共子序列本身，因此dp数组的设计需要注意

转移方程： dp[i][j][k]：为在三个字符串分别在i,j，k位置时，的最长的公共子序列字符串本身

dp[i][j][k] = dp[i-1][j-1][k-1] + str[i], 当str1[i] == str2[j] == str3[k]

dp[i][j][k] = min(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]) , 当str1[i] != str2[j] != str3[k]

代码：

#include<vector>
#include <map>
using namespace std;
/*
输入：
abcd acb abc
输出：
ab
*/
int main() {
	string s1, s2, s3;
	cin >> s1 >> s2 >> s3;
	int n1 = s1.size();
	int n2 = s2.size();
	int n3 = s3.size();
	s1 = " " + s1;
	s2 = " " + s2;
	s3 = " " + s3;
	vector<vector<vector<string>>> dp(n1 + 1, vector<vector<string>>(n2 + 1, vector<string>(n3 + 1, "")));
	for (int i = 1; i <= n1; i++) {
		for (int j = 1; j <= n2; j++) {
			for (int k = 1; k <= n3; k++) {
				if (s1[i] == s2[j] && s1[i] == s3[k]) {
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + s1[i];
				}
				else {
					if (dp[i - 1][j][k].size() > dp[i][j - 1][k].size() && dp[i - 1][j][k].size() > dp[i][j][k-1].size()) {
						dp[i][j][k] = dp[i - 1][j][k];
					}
					else if (dp[i][j - 1][k].size() > dp[i - 1][j][k].size() && dp[i][j - 1][k].size() > dp[i][j][k - 1].size()) {
						dp[i][j][k] = dp[i][j - 1][k];
					}
					else {
						dp[i][j][k] = dp[i][j][k - 1];
					}
				}
			}
		}
	}
	cout << dp[n1][n2][n3] << endl;
}