动态规划：最长公共子序列

动态规划：最长公共子序列

给定两个字符串，求这两个字符串最长的公共子序列，如 string str1 = "abcdefg";string str2 = "agcdfbdfg;" 最长公共子序列是acdfg或abdfg。

#include 
#include 
#include 
using namespace std;

int func(string str1, string str2, vector<vector<int>>& dp, vector<vector<int>>& path)
{
	for (int i = 0; i < str1.size(); i++)
	{
		for (int j = 0; j < str2.size(); j++)
		{
			if (str1[i] == str2[j])
			{
				dp[i + 1][j + 1] = dp[i][j] + 1;
				path[i + 1][j + 1] = 0; //对角线
			}
			else
			{
				if (dp[i][j + 1] >= dp[i + 1][j])//选上 左上相等默认选上
				{
					dp[i + 1][j + 1] = dp[i][j + 1]; 
					path[i + 1][j + 1] = 1; 
				}
				else//选左 
				{
					dp[i + 1][j + 1] = dp[i + 1][j];
					path[i + 1][j + 1] = 2; 
				}
			}
		}
	}
	return dp[str1.size()][str2.size()];
}

void printStr(string str1, int i, int j, vector<vector<int>>& path)
{
	if (i <= 0 || j <= 0) return;	
	if (path[i][j] == 0)//对角线，先递归再打印
	{
		printStr(str1, i - 1, j - 1, path);
		cout << str1[i-1];
	}
	else if (path[i][j] == 1)//向上递归
	{
		printStr(str1, i - 1, j, path);
	}
	else //向左递归
	{
		printStr(str1, i, j - 1, path);
	}
}

int main()
{
	string str1 = "abcdefg";
	string str2 = "agcdfbdfg";

	vector<vector<int>> dp(str1.size()+1, vector<int>(str2.size()+1, 0));
	vector<vector<int>> path(str1.size()+1, vector<int>(str2.size()+1, -1));

	cout << func(str1, str2, dp, path) << endl;
	printStr(str1, str1.size(), str2.size(), path);
	cout << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65