题解 | #牛可乐和最长公共子序列#

对于s1的某个位置i，s2的某个位置j。这两个位置之前的最长公共子序列等于=如果这两个位置相同的话就是前面的位置加一。如果不同的话就得比较s1前一位或s2前一位谁比较大了。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 5000+10;
int dp[maxn][maxn];
string s1, s2;

int main() {
    while (cin>>s1>>s2) {
        if (s1[0]==s2[0]) dp[1][1] = 1;
//         memset(dp,0,sizeof(dp));
        int ans = 0;
        for (int i=1;i<=s1.size();i++) {
            for (int j=1;j<=s2.size();j++) {
                if (s1[i-1]==s2[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[s1.size()][s2.size()]<<endl;
    }
    
    return 0;
}