动态比较两个字符串的公共部分的长度，由最小的子问题的最优解渐进得到最整个问题的优解。 参考
#include<bits/stdc++.h> using namespace std; string A,B; int best[100][100]; int dp() { for(int i=1;i<=A.size();++i)#A字符串的前i个部分 { for(int t=1;t<=B.size();++t)#B字符串的前t个部分 { if(A[i-1]==B[t-1]) best[i][t]=best[i-1][t-1]+1;; else best[i][t]=max(best[i-1][t],best[i][t-1]); } } return best[A.size()][B.size()]; } int main() { while(true) { cin>>A>>B; cout<<dp(); } }