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

没想到这里能做到一道经典的LCS经典的模板问题

//经典的求解两个序列的最长公共子序列的长
//LCSd的经典模版问题
#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;
}

``
这里的状态又不一样了，只有两个参数的问题