lcs.md

最长公共子序列

1.概念解释

一个数列，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列

例如：序列<A,B,C,B,A>，<A,B,B,A,C>,则可以有子序列<A,B>,<A,B,B>,<A,B,B,A>,其中<A,B,B,A>就是这两个序列中最长的公共子序列

以下是部分子序列

2.最长公共子序列应用

• Diff工具

• Git等版本控制工具

• 相似资料搜索

3.动态规划解法

1.划分子问题

​ 定义序列X={x₁,x₂,…,x_i},Y={Y₁,Y₂,…,Y_j}

​ 序列Z为XY的最长公共子序列,Z={Z₁,Z₂,Z₂,…,Z_k}

2.推导

​ Z有三种情况

​ 1.X_i=Y_j,则Z_k=X_i=Y_j,并且Z_k-1为X_i-1与Y_j-1的最长公共子序列

​ 2.X_i≠Y_j,则Z_k,为X_i-1与Y_j的最长公共子序列

​ 3.X_i≠Y_j,则Z_k,为X_i与Y_j-1的最长公共子序列

​ 依次类推,可推导出公式：

​ 参考实现