【c++】【算法】【动态规划】最长公共子序列

【c++】【算法】【动态规划】最长公共子序列

//递归方式
//最长公共子序
//直接递归 求最长公共子序长度
int FindValue(const string& X, const string& Y, int i, int j)
{
	if (i == 0 || j == 0)return 0;
	if (X[i] == Y[j])return FindValue(X, Y, i - 1, j - 1)+1;
	else return std::max(FindValue(X, Y, i, j - 1), FindValue(X, Y, i - 1, j));
}

//动态规划 //递归+表保存 求最长公共子序长度
int FindValue1(const string& X, const string& Y, vector<vector<int>>& vec, int i, int j)
{
	if (i <= 0 || j <= 0)return 0;
	if (vec[i][j] > 0)return vec[i][j];
	else if (X[i] == Y[j])
	{
		vec[i][j] = FindValue1(X, Y, vec, i - 1, j - 1)+1;
	}
	else
	{
		int t1= FindValue1(X, Y, vec, i, j - 1);
		int t2= FindValue1(X, Y, vec, i-1, j);
		
		vec[i][j] = max(t1, t2);
	}
	return vec[i][j];
}
//动态规划 递归+打印出子序列 //求最长公共子序是什么
//不使用路径数组，直接回溯 dp 数组得到 LCS
//通过递归 + 表格计算并回溯 LCS
void printLCS(int i, int j, const string& X, const string& Y, vector<vector<int>>& dp, string& lcs) {
	// 递归终止条件
	if (i <=0 || j <=0) {
		return;
	}

	// 如果当前字符相等，加入 LCS
	if (X[i] == Y[j]) {
		lcs = X[i] + lcs;
		printLCS(i - 1, j - 1, X, Y, dp, lcs);  // 同时回溯
	}
	// 如果字符不相等，向 dp 数组的较大值处回溯
	else {
		if (dp[i - 1][j] >= dp[i][j - 1]) {
			printLCS(i - 1, j, X, Y, dp, lcs);  // 向上回溯
		}
		else {
			printLCS(i, j - 1, X, Y, dp, lcs);  // 向左回溯
		}
	}
}
//使用路径数组
//1 代表行=列 2代表行-1 3代表列-1
int FindValue2(const string& X, const string& Y, vector<vector<int>>& vec, vector<vector<int>>& dest, int i, int j)
{
	if (i <= 0 || j <= 0)return 0;
	if (vec[i][j] >0 )return vec[i][j];//**
	else if (X[i] == Y[j])
	{
		vec[i][j] = FindValue2(X, Y, vec, dest, i - 1, j - 1) + 1;
		dest[i][j] = 1;
	}
	else
	{
		int t1 = FindValue2(X, Y, vec, dest, i - 1, j);
		int t2 = FindValue2(X, Y, vec, dest, i, j - 1);
		if (t1 > t2)
		{
			vec[i][j] = t1;
			dest[i][j] = 2;
		}
		else
		{
			vec[i][j] = t2;
			dest[i][j] = 3;
		}
	}
	return vec[i][j];

}
void Print(vector<vector<int>>& vec)
{
	int n = vec.size();
	for (int i = 1;i < n;i++)
	{
		for (int j = 1;j < vec[i].size();j++)
		{
			cout << vec[i][j] << " ";
		}
		cout << endl;
	}
}
void printPublicSub(vector<vector<int>>& dest, int i, int j,string&X)
{
	if (i <= 0 || j <= 0)return;
	if (dest[i][j] == 1)
	{
		printPublicSub(dest, i - 1, j - 1,X);
		cout << X[i] << " ";
	}
	else if (dest[i][j] == 2)
	{
		printPublicSub(dest, i - 1, j, X);
	}
	else
	{
		printPublicSub(dest, i, j-1, X);
	}
}

//非递归方式 求最长公共子序长度
int FindValue3(const string& X, const string& Y, int m, int n)
{
	vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));

	for (int i = 1;i <= m;i++)
	{
		for (int j = 1;j <= n;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]);
			}
		}
	}

	return dp[m][n];
}
//非递归方式 求最长公共子序是什么
int FindValue4(const string& X, const string& Y, int m, int n,string &lcs)
{
	vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));

	for (int i = 1;i <= m;i++)
	{
		for (int j = 1;j <= n;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]);
			}
		}
	}
	
	// 从 dp 数组回溯得到 LCS
	int i = m, j = n;
	while (i > 0 && j > 0) {
		if (X[i] == Y[j]) {
			lcs = X[i - 1] + lcs;  // 字符匹配，加入 LCS
			i--;
			j--;
		}
		else if (dp[i - 1][j] > dp[i][j - 1]) {
			i--;  // 向上回溯
		}
		else {
			j--;  // 向左回溯
		}
	}

	return dp[m][n];
}

int main()
{
	string X = "#ABCBDAB";
	string Y = "#BDCABA" ;
	int i = X.size()-1;
	int j = Y.size()-1;
	
	vector<vector<int>>vec1(i + 1, vector<int>(j + 1, 0));
	
	//int n = FindValue1(X, Y, vec1, i, j);
	//cout << n << endl;
	//Print(vec1);
	// 回溯 dp 数组得到具体的 LCS
	//string lcs;
	//printLCS(i, j,X,Y,vec1, lcs);
	//cout << lcs << endl;
	//cout << "---------------------------" << endl;
	//cout << "---------------------------" << endl;
	//vector<vector<int>>vec(i + 1, vector<int>(j + 1, 0));
	//vector<vector<int>>dest(i + 1, vector<int>(j + 1, 0));
	//int m=FindValue2(X, Y, vec,dest,i,j);
	
	//cout << m << endl;
	//cout << "---------------------------" << endl;
	//Print(vec);
	//cout << "---------------------------" << endl;
	//Print(dest);
	//cout << "---------------------------" << endl;
	//printPublicSub(dest, i, j, X);

	//int m = FindValue3(X, Y, i, j);
	//cout << m << endl;

	//string lcs;
	//int m=FindValue4(X, Y, i, j,lcs);
	//cout << m << endl;
	//cout << lcs << endl;


	
}