描述

给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
数据范围 : 1\leq m,n\leq 10001≤m,n≤1000 。保证字符串中的字符只有小写字母。
要求：空间复杂度 O(mn)O(mn)，时间复杂度 O(mn)O(mn)
进阶：空间复杂度 O(min(m,n))O(min(m,n))，时间复杂度 O(mn)O(mn)

输入描述：

第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。
接下来第二行和第三行分别输入一个字符串 s1 和 s2。

输出描述：

输出两个字符串的最长公共子序列的长度

示例1

输入： 
5 6
abcde
bdcaaa
复制
输出： 
2
复制
说明： 
最长公共子序列为 "bc" 或 "bd" ，长度为2   

示例2

输入： 
3 3
abc
xyz
复制
输出： 
0
解题思路：最长公共子序列问题只能是动态规划来解决了，需要画表来理解其状态转移的计算 
dp[i][j]s1的前i个元素和s2的前j个元素的最长公共子序列的长度

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        string s1;
        string s2;
        cin >> s1;
        cin >> s2;
        // dp[i][j]s1的前i个元素和s2的前j个元素的最长公共子序列的长度
        vector<vector<int>>dp(n+1, vector<int>(m+1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        
        cout << dp[n][m] << endl;
        return 0;
    }
}
// 64 位输出请用 printf("%lld")