很显然的最长公共子序列（LCS）的板子。
定义：用dp[i][j]表示S1前i位和S2前j位的最长公共子序列。
状态转移：
很显然是对的。
大胆猜想，无需证明！
在相等的时候加一，结果一定不会比不加差，所以加一即可。
时间复杂度：O(n2)。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 string s1,s2; 5 int l1,l2,dp[10005][10005]; 6 int main() 7 { 8 cin>>s1>>s2; 9 l1=s1.length(); 10 l2=s2.length(); 11 for(int i=1;i<=l1;i++){ 12 for(int j=1;j<=l2;j++){ 13 if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; 14 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 15 } 16 } 17 cout<<dp[l1][l2];; 18 return 0; 19 }
//AHOI2004 Day1t1
洛谷 P2543 [AHOI2004]奇怪的字符串（LCS模板）
原文：https://www.cnblogs.com/yinyuqin/p/12142825.html