DP(最长公共子序列)

Description

在字母表中,分别给出两个长度为n和m的字符串A和B,确定在A与B中最长公共子序列的长度。

\(A = a_1a_2a_3...a_n\) 其中每个\(i_j\)都在1和n之间,并且\(1<=i_1<i_2<...<i_k<=n\)

Solution

使用动态规划解决这个问题,\(A = a_1a_2a_3...a_n\)\(B = b_1b_2b_3...b_n\),令\(L[i,j]\)来表示两个公共子序列的长度。那么总结有以下的结论:

\[ L[i,j] = \left\{\begin{matrix} & 0 & 若i=0或j=0\\ & L[i-1,j-1]+1 & 若i>0,j>0 和 a_i=b_j\\ & max\left\{L[i,j-1],L[i-1,j] \right\} & 若i>0,j>0 和a_i \neq b_j \end{matrix}\right. \]

Algotrithm

算法: LCS
输入: 字母表上的两个字符串A和B,长度分别为n和m
输出: A和B最长公共子序列的长度

1. for i = 0 to n
2. L[i, 0] = 0
3. end for
4. for j = 0 to m
5. L[0, j] = 0
6. end for
7. for i = 1 to n
8. for j = 1 to m
9. if a_i = b_j then L[i,j] = L[i-1,j-1]+1
10. else L[i,j] = max{L[i,j-1],L[i-1,j]}
11. end if
12. end for
13. end for
14. return L[n,m]