LCS:最长公共子序列
对于两个长度为n的序列，要求最长公共子序列，我们可以用dp[i][j]表示a序列的前i位和b序列的前j位的最长公共子序列，最后dp[n][n]就是答案。
状态转移： if(a[i]!=b[j]) dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
代码：
long long a[1010], b[1010]; long long dp[1010][1010]; int main() { long long n, ans = 0; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); for (int i = 1; i <= n; i++) scanf("%lld", &b[i]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1; } } cout << dp[n][n] << endl; return 0; }