动态规划-最长公共子序列
最长公共子序列（Longest Common Subsequence，LCS）又叫最长公共子串（不要求连续）。
其定义是：一个序列 S ，如果分别是两个或多个已知序列的子序列，且所有符合此条件序列中最长的，则 S 为已知序列的最长公共子序列。
【输入描述】
输入2行。第一行输入字符串 S1 ，第二行输入字符串 S2。
【输出描述】
输出1行。输出最长公共子序列的长度。
【输入样例】
123abc
abc123abc
【输出样例】
6
【参考程序】
//小牛编程
#include <bits/stdc++.h>
using namespace std;
string s1, s2;
int dp[1001][1001];
int main() {
cin >> s1;
cin >> s2;
for (int i = 1; i <= s1.length(); i++)
for (int j = 1; j <= s2.length(); j++) {
if (s1[i] == s2[j])
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.length()][s2.length()] << endl;
return 0;
}