2086: 蓝桥杯算法提高VIP-最长公共子序列

解题思路:

（1）最长公共子序列和最长公共子串的区别是，前者可以不连续，后者必须是连续的。

（2）因此在构造状态转移方程时，比较的两个字母不相同时，前者的最优解为不包含任意一个字母的两个子串的最优解的较大者，而后者的最优解为0。

（3）在输出结果时，前者输出的是存储结果的数组的最后一个数，后者需要遍历二维数组输出最大值，而非最后一个数。

注意事项:

好像用string比用char*传参方便，以后决定不用char*了。

参考代码:

// 题目 2086: 蓝桥杯算法提高VIP-最长公共子序列
#include <iostream>
#include <cstring>

using namespace std;

int longestCommonSubsequence(string str1, string str2); // lcs
int main() {
	// 读输入
	string str1;
	string str2;
	cin >> str1 >> str2;

	cout << longestCommonSubsequence(str1, str2) << endl;
	return 0;
}

int longestCommonSubsequence(string str1, string str2) {
	int len1 = str1.size(); // str1的长度
	int len2 = str2.size(); // str2的长度
	int res[len1 + 1][len2 + 1]; // 存储最优解，res[i][j]代表包含str1前i个和str2前j个元素的子串的lcs
	memset(res, 0, sizeof(res)); // 初始化
	for (int i = 1; i < len1 + 1; i++) {
		for (int j = 1; j < len2 + 1; j++) {
			if (str1[i - 1] == str2[j - 1]) {
				res[i][j] = res[i - 1][j - 1] + 1; // 同一个字母，返回不包含这两个字母的子串的最优解+1
			} else {
				res[i][j] = max(res[i - 1][j], res[i][j - 1]); // 不同，返回不包含任意一个字母的子串的最优解
			}
		}
	}
	return res[len1][len2]; // 返回最后一个值，即str1和str2的最优解
}