题解 | #最长公共子序列（一）【模板】#

#include <iostream>
#include <string>
#include <vector>

int main(int argc, char *argv[]) {
  int res = 0;
  int len1, len2;
  std::string str1, str2;
  
  std::cin >> len1 >> len2;
  std::cin >> str1;
  std::cin >> str2;
  
  //  str1是最短的字符串
  if (len1 > len2) {
    std::swap(str1, str2);
    std::swap(len1, len2);
  }
  
  //  str1字符串长度为i，str2字符串长度为j的子序列的长度 （该子序列并非以下标ij结尾，而是截止到该下标为止出现过的）
  std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1, 0));
  
  for (int i = 1; i <= len1; ++i) {
    for (int j = 1; j <= len2; ++j) {
      if (str1[i - 1] == str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  
  std::cout << dp[len1][len2] << std::endl;
  
  return 0;
}