最长公共子序列的动态规划解法

最长公共子序列问题：给定两个序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }，找出 X 和 Y 的最长公共子序列。

 

一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列 X 和 Y ，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X 和 Y 的公共子序列。例如，若 X = {A， B， C， B， D， A， B }，Y = {B， D， C， A， B， A }，序列{B， C， A }是 X 和 Y 的一个公共子序列，序列{B， C， B， A }也是 X 和 Y 的一个公共子序列，且为最长公共子序列。

 

最长公共子序列问题具有最优子结构性质。

设序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }的最长公共子序列为 Z = {z1, z2, ......, zk}，则

（1） 若 xm = yn ，则 zk = xm = yn ，且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列。

（2） 若 xm != yn 且 zk != xm ，则 Z 是 Xm-1 和 Y 的最长公共子序列。

（3） 若 xm != yn 且 zk != yn ，则 Z 是 X 和 Yn-1 的最长公共子序列。

其中， Xm-1 = {x1,