序列——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 ,
更多推荐
最长公共子序列——LCS(c/c++ 伪代码)
发布评论