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

由于dp[i][j]只和d[i-1][j-1],dp[i-1][j],dp[i][j-1]有关，可以优化使用空间大小，增加几个临时变量，

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

int main() {
    string s1,s2;
    int n,m;
    cin >> n >> m;
    cin >> s1 >> s2;
    if (s1.size() > s2.size()) {
        swap(n, m);
        swap(s1,s2);
    }
    vector<int> f(m+1,0);
    int res = 0;
    for (auto i=1; i<=n; i++) {
        auto left_up=0,last=0;
        for (auto j=1; j<=m; j++) {
            auto tmp = left_up;
            left_up = f[j];
            if (s1[i-1] == s2[j-1]) {
                // f[i][j] = f[i-1][j-1] + 1;
                f[j] = tmp + 1;
            }
            else {
                // f[i][j] = max(f[i-1][j],f[i][j-1]);
                f[j] = max(f[j], last);
            }

            last = f[j];
            res = max(res,f[j]);
        }
    }
    cout << res << endl;
}