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

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main(){
    int m,n,i,j;
    int L[1001][1001];
    scanf("%d%d\n",&m,&n); //注意要输入换行符
    char x[m],y[n];
    cin>>x;
    getchar();//消耗掉多余的换行符
    for (j = 0; j < n; ++j) {
        scanf("%c",&y[j]);
    }

    for (i = 0; i <= n; ++i) {  //初始化第0行
        L[0][i] = 0;
    }
    for (j = 0; j <= m; ++j) { //初始化第0列
        L[j][0] = 0;
    }
    for (i = 1; i <= m; ++i) {
        for (j = 1; j <=n ; ++j) {
            if (x[i - 1] == y[j - 1]){ //这里需要从第0个下标开始遍历
                L[i][j] = L[i - 1][j - 1] + 1;
            } else if ( L[i][j - 1] >= L[i - 1][j]){
                L[i][j] = L[i][j - 1];
            } else{
                L[i][j] = L[i - 1][j];
            }
        }
    }
    printf("%d",L[m][n]);

}