[编程题]:最长公共子序列（LCS）
[编程题]:最长公共子序列（LCS）
题目描述：给定两个字符串（或数字序列）A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以是补连续的）
例如：“sadstory” 和 “adminstory” 的最长公共子序列是 “adstory”，长度为6
动态规划（Dynamic Programming）
令dp[i][j]表示A的i号位和B的j号位之间的LCS的长度（小标从1开始），如dp[4][5]表示"sads"和"admin"的LCS长度。那么可以根据A[i]和B[j]的情况，分成两种策略：
- 若A[i] == B[j]，则字符串A和B的LCS增加了1位，即有dp[i][j] = dp[i - 1][j - 1] + 1;
- 若A[i] != B[j]，则字符串A和字符串B之间的LCS的最大长度继承自dp[i - 1][j]和dp[i][j - 1]的最大者，即dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
根据以上分析得到了动态规划的转移方程，就可以写出代码了：
Java
C++