要努力。。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int N = 0, M = 0;
cin >> N >> M;
vector<char> str1 (N + 10);
vector<char> str2 (M + 10);
// state[i][j]表示 str1的前i个字符 和 str2的前j个字符 最长公共子序列是多少
/*
在状态拆分时,对于[i, j],我们可以什么都不选,即 state[i][j] = state[i - 1][j - 1]
也可以选i不选j,选j不选i,和都选
都选的话,如果str1[i] == str2[j], 则 state[i][j] = state[i - 1][j - 1] + 1
中间两种情况(选i不选j,选j不选i)比较难 这是因为我们选j 需要确保str1的前i-1个字符组成的
最长序列是以str2[j]为结尾的
但是这种情况很难去判断
但是 state[i - 1][j]已经包含这种情况了 选j不选i同理 因此直接取最大即可
此外state[i - 1][j - 1]的情况也被包含在了state[i - 1][j]或state[i][j - 1]中
因此可以不算
得到的启示就是 对于求max这种 集合的划分(状态的更新步)可以重复 但不能遗漏
但如果是计数类 就不能重复 更不能遗漏
*/
for (int i = 1; i < N + 1; i ++)
cin >> str1[i];
for (int i = 1; i < M + 1; i ++)
cin >> str2[i];
vector<vector<int>> state (N + 10, vector<int> (M + 10, 0));
for (int i = 1; i < N + 1; i ++) {
for (int j = 1; j < M + 1; j ++) {
state[i][j] = max(state[i - 1][j], state[i][j - 1]
);
if (str1[i] == str2[j]) state[i][j] = max(state[i][j], state[i - 1][j - 1] + 1);
}
}
cout << state[N][M] << "\n";
return 0;
}