LCS最长公共子序列【c++】

题目描述：

我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度

输入描述：

输入包含多组数据。
每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024

输出描述：

对应每组输入，输出最长公共子序列的长度。

示例：

输入
abcfbc abfcab
programming contest
abcd mnp
输出
4
2
0

解题思路：

1、一个简单的例子：

解释：
1、填表
a和a的最大公共子串数目为1
a和ab的最长公共子串数目为1
……
ac和a的最长公共子串为1
ac和ab的最长公共子串为1
……
以此类推计算上述该表
2、推导状态转移方程
设上述二维数组为dp[5][6]
右下角为最长公共子序列长度及题解
状态转移方程为：
dp[i][j]=dp[i-1][j-1]+1 (a[i]=b[j])
dp[i][j]=max(dp[i-1][j],dp[i][j-1])

代码：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	string A, B;
	while (cin >> A >> B)
	{
		int alen = A.length();
		int blen = B.length();
		vector<vector<int>>dp(alen, vector<int>(blen, 0));
		/*if (A[0] == B[0])
		{
			dp[0][0] = 1;
		}
		else
		{
			dp[0][0] = 0;
		}*/
		dp[0][0] = (A[0] == B[0]) ? 1 : 0;
		for (int i = 1; i < alen; i++)
		{
			dp[i][0] = (A[i] == B[0]) ? 1 : 0;
			dp[i][0] = max(dp[i - 1][0], dp[i][0]);
		}
		for (int j = 1; j < blen; j++)
		{
			dp[0][j] = (A[0] == B[j]) ? 1 : 0;
			dp[0][j] = max(dp[0][j-1], dp[0][j]);
		}
		for (int i = 1; i < alen; i++)
		{
			for (int j = 1; j < blen; j++)
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				if (A[i] == B[j])
				{
					dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
			}
		}
		cout << dp[alen - 1][blen - 1]<<endl;
	}
	return 0;
}

链接：https://www.nowcoder.com/questionTerminal/9ae56e5bdf4f480387df781671db5172
来源：牛客网