解题思路：动态规划

首先使用二维dp，令dp[i][j]表示s1的前i个字符构成的字符串和s2的前j个字符构成的字符串的最长公共子序列。

那么有状态转移方程：

当s1[i] == s2[j]时，dp[i + 1][j + 1] = dp[i][j] + 1；否则 dp[i + 1][j + 1] = max ( dp[i][j + 1], dp[i + 1][j] )

时间复杂度O(mn)，空间复杂度O(mn)。

空间压缩，dp数组由二维压缩到一维

注意到动态转移方程中的 i+1只和 i 有关，因此可以将dp数组压缩到一维。

注意到题目要求的空间复杂度为 O(min(m, n))，我们强制令n >= m，如果 n < m 则交换m和n，交换s1和s2。

这样开的dp数组长度为m + 1最小，符合O(min(m, n))。

下面给出完整代码。

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

int main() {
    int n, m;
    string s1, s2;
    cin >> n >> m;
    if(n < m) {
        cin >> s2 >> s1;
        swap(m, n);
    } else {
        cin >> s1 >> s2;
    }
    vector<int> dp(m + 1, 0);
    for(int i = 0; i < n; ++i) {
        int lastDp = 0; //表示上一项，即二维的dp[i][j]，初始为dp[i][0] = 0
        for(int j = 0; j < m; ++j) {
            int tmp = dp[j + 1]; //临时记录当前项，即二维的dp[i][j+1]
            if(s1[i] == s2[j]) {
                dp[j + 1] = lastDp + 1; //即dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[j + 1] = max(dp[j + 1], dp[j]); //即dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j])
            }
            lastDp = tmp; //更新上一项为之前临时记录的
        }
    }
    cout << dp[m];
}
// 64 位输出请用 printf("%lld")