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

#include <bits/stdc++.h>

using namespace std;

//4MB，超过局部变量的内存了，变成全局变量=>new申请堆空间
int dp[1002][1002];//dp[i][j] s1的前i个元素， s2的前j个元素 的最大公共长度

int main() {
    int n;
    int m;
    char s1[1001];
    char s2[1001];
    scanf("%d%d", &n, &m);
    scanf("%s%s", &s1, &s2);


    //初始化小问题
    for (int j = 0; j <= m; ++j) {
        dp[0][j] = 0;
    }
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 0;
    }

    //
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            //s1[0]~s1[i-1]和s2[0]~s2[j-1]
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    std::cout << dp[n][m] << std::endl;
    return 0;
}