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

相当于 缓存前面计算的状态，推导下一个状态

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



int main() {
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    //todo vaid n
    vector<vector<int> >  lcm(n + 1, vector<int>(m + 1) );

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j]) {
                // dp[i-1][j-1] + 1
                if (i - 1 >= 0 && j - 1 >= 0) {
                    lcm[i][j] = lcm[i - 1][j - 1] + 1;
                } else {
                    lcm[i][j] = 1;
                }
            } else {
                lcm[i][j] = max(i - 1 >= 0 ? lcm[i - 1][j] : 0, j - 1 >= 0 ? lcm[i][j - 1] : 0);
            }
        }
    }
    cout << lcm[n - 1][m - 1];
    return 0;
}