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

#include <iostream>
using namespace std;

int dp[1010][1010];
int main() {
    int n,m;cin>>n>>m;
    string a,b;cin>>a>>b;
    // a = a+"@";
    // b = b+"#";
    for(int i = 0;i<=n;i++){
        dp[i][0] = 0;
    }
    for(int j = 0;j<=m;j++){
        dp[0][j] = 0;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(a[i-1]==b[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}
// 64 位输出请用 printf("%lld")

dp[i][j]数组表示字符串a前i个字符和字符串b前j个字符相等的字符个数，他只有三个值为相等时为dp[i-1][j-1]+1,不等时dp[i][j-1],dp[i-1][j]。

活动地址https://www.nowcoder.com/discuss/726480854079250432