题解 | 最长公共子序列(一)

DP的模板题

将s1作为短的字符串，s2作为长的字符串。

考虑空间复杂度n*m的做法，定义dp[n][m]，dp[i][j]表示考虑s2的前 i 位和s1的前 j 位的最长公共子序列的结果

状态转移：

if (s2[i] == s1[j]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + 1);

else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

考虑到在转移方程中，只存在两行数组之间的转换，既只有dp[i][*]和dp[i - 1][*]的转换。可以使用一个两行的数组来代替整个数组。既可以做到时间复杂度min(n, m);

#include <bits/stdc++.h>
using namespace std;

int main() {

    int n, m;
    cin >> n >> m;
    string s1, s2;
    cin >> s1 >> s2;
  
    if(n > m) {
        int t = n;
        n = m;
        m = t;
        string x = s1;
        s1 = s2;
        s2 = x;
    }
    vector<vector<int>> dp(2, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (s2[i] == s1[j]) {
                dp[1][j + 1] = max(dp[0][j + 1], dp[0][j] + 1);
            } else {
                dp[1][j + 1] = max(dp[0][j + 1], dp[1][j]);
            }
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = dp[1][j];
        }
    }
    cout << dp[0][n] << '\n';
}