状态表示

dp[i][j]，表示A的前i个字符和B的前j个字符构成的所有子序列中的最大长度

状态转移

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

如果 a[i] == b[j] 还要加上dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)

优化

dp数组其实可以压缩为一维的，根据状态转移方程知道只需要记录下dp[i - 1][j - 1]即可，我用last, now两个整形来维护

#include <iostream>
using namespace std;

const int NN = 1010;
int N, M, dp[NN];   // 压缩成一维的了
char a[NN], b[NN];

int main(){
    cin >> N >> M;
    cin >> a + 1; cin >> b + 1;  // 细节：从 a[1] b[1] 开始存储
    int last, now;
    for (int i = 1; i <= N; i ++){
        last = 0;         // 每行最开始的时候要把 last 置为0 !!!!
                          // 因为此时 last 就是 dp[i - 1][0]
        for (int j = 1; j <= M; j ++){
            now = dp[j];
            dp[j] = max(dp[j - 1], dp[j]);
            if (a[i] == b[j]) dp[j] = max(dp[j], last + 1);
            last = now;
        }
    }
    cout << dp[M];

    return 0;
}