在线提交(不支持C#): https://www.lintcode.com/problem/longest-common-subsequence/
一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。例如,”ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是)。 给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。
说明
样例 给出“ABCD” 和 “EDCA”,这个LCS是 “A” (或 D或C),返回1 给出 “ABCD” 和 “EACB”,这个LCS是“AC”返回 2
注意: 序列可以不连续。
Tags: Longest Common Subsequence LintCode Copyright Dynamic Programming(DP)
分析: 将算式的计算结果记录在内存中,需要时直接调用该结果,从而避免无用的重复计算,提高处理效率,这在程序和算法设计中是一种行之有效的手法。动态规划就是这类手法之一。
事实上动态规划是一种记忆化递归(memorized recursive),缓存部分重要数据。另外,动态规划法可以建立递归式,通过循环顺次求出最优解。
为方便说明,这里我们用XiXiX_i代表{x1,x2,⋯,xix1,x2,⋯,xix_1,x_2,\cdots,x_i},用YjYjY_j代表{y1,y2,⋯,yjy1,y2,⋯,yjy_{1},y_{2},\cdots,y_{j} }。那么,求长度分别为m、n的两个序列X、Y的LCS,就相当于求XmXmX_m与YnYnY_n的LCS。我们将其分割为局部问题进行分析。
首先,求XmXmX_m与YnYnY_n的LCS时要考虑以下两种情况:
这个算法对XiXiX_i与YjYjY_j同样适用。于是可准备下述函数,用来求解LCS的局部问题。
c[m+1][n+1]: 该二维数组中,c[i][j] 代表XiXiX_i与YjYjY_j的LCS的长度
c[i][j] 的值可由下述递推公式(Recursive Formula)求得。
c[i][j]=⎧⎩⎨0c[i−1][j−1]+1max(c[i][j−1],c[i−1][j])i=0 || j=0i,j>0 and xi=yji,j>0 and xi≠yjc[i][j]={0i=0 || j=0c[i−1][j−1]+1i,j>0 and xi=yjmax(c[i][j−1],c[i−1][j])i,j>0 and xi≠yj
c[i][j]=\begin{cases} 0 & i = 0 \ || \ j =0 \\ c[i-1][j-1] + 1 & i,j >0 \ and \ x_i = y_{j} \\ max(c[i][j-1], c[i-1][j]) & i,j >0 \ and \ x_i ≠ y_{j} \end{cases}
基于上述变量和公式,可以用动态规划法求序列X与Y的LCS。
已AC代码如下:
class Solution {
public:
int longestCommonSubsequence(string &A, string &B) {
int m = A.size();
int n = B.size();
int **c = (int **)malloc((m+1) * sizeof(int *));
for (int i = 0; i < m + 1; i++)
c[i] = (int *)malloc((n+1) * sizeof(int));
int max1 = 0;
A = ' ' + A;
B = ' ' + B;
for (size_t i = 1; i <= m; i++)
c[i][0] = 0;
for (size_t j = 1; j <= n; j++)
c[0][j] = 0;
for (size_t i = 1; i <= m; i++)
{
for (size_t j = 0; j <= n; j++)
{
if (A[i] == B[j])
{
c[i][j] = c[i - 1][j - 1] + 1;
}
else
c[i][j] = max(c[i][j - 1], c[i - 1][j]);
max1 = max(max1, c[i][j]);
}
}
return max1;
}
};
Rank: 您的提交打败了 92.60% 的提交.
扩展阅读: 最长公共子序列问题 - Fogsail Chen - SegmentFault 思否 https://segmentfault.com/a/1190000008521545