题解 | #牛可乐和最长公共子序列#
牛可乐和最长公共子序列
https://ac.nowcoder.com/acm/problem/235624
对于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;
}
