最长公共子序列——LCS(c/c++ 伪代码)

序列——LCS(c/c++ 伪代码)"/>

最长公共子序列——LCS(c/c++ 伪代码)

问题定义

• 子序列
  对 于 给 定 序 列 X = < x 1 , x 2 , . . . , x m > ， Z = < z 1 , z 2 , . . . z k > 存 在 一 个 严 格 递 增 的 X 的 下 标 序 列 < i 1 , i 2 , . . . , i k > ， 对 所 有 j = 1 , 2 , . . . , k 满 足 x i j = z j 对于给定序列X=<x_1,x_2,...,x_m>，Z=<z_1,z_2,...z_k>\\ 存在一个严格递增的X的下标序列<i_1,i_2,...,i_k>，对所有j=1,2,...,k\\ 满足x_{i_j}=z_j 对于给定序列X=<x1​,x2​,...,xm​>，Z=<z1​,z2​,...zk​>存在一个严格递增的X的下标序列<i1​,i2​,...,ik​>，对所有j=1,2,...,k满足xij​​=zj​
  则称Z为X的子序列

• 公共子序列

  Z既是X的子序列，也是Y的子序列

• 问题描述

  给定两个序列
  X = < x 1 , x 2 , . . . , x m > , Y = < y 1 , y 2 , . . . , y n > X=<x_1,x_2,...,x_m>,Y=<y_1,y_2,...,y_n> X=<x1​,x2​,...,xm​>,Y=<y1​,y2​,...,yn​>
  求X和Y的长度最长的公共子序列

应用动态规划算法

1. 刻画最长公共子序列的特征

LCS最优子结构

令 X = < x 1 , x 2 , . . . , x m > , Y = < y 1 , y 2 , . . . , y n > X=<x_1,x_2,...,x_m>,Y=<y_1,y_2,...,y_n> X=<x1​,x2​,...,xm​>,Y=<y1​,y2​,...,yn​>为两个序列， Z = < z 1 , z 2 ,