当前位置: 代码迷 >> 综合 >> LCS-DP
  详细解决方案

LCS-DP

热度:82   发布时间:2024-01-18 23:42:58.0

longest  common sequence最长公共子序列

不一定要连续的公共序列

比如ABCDEF

ASSBWWC也有ABC作为最长公共子序列

longest common substring 最长公共子串才是连续的


暴力求解方式:


公共子序列的解决方式:

设X = <x1,x2...xm>, Y = <y1,y2...yn>为两个序列,并设Z = <z1,z2...zk>为X和Y的任意一个LCS。可以得出:

1、如果xm = yn,那么zk = xm = yn而且Z(k-1)是X(m-1)和Y(n-1)的一个LCS;

2、如果xm != yn,那么zk != xm蕴含Z是X(m-1)和Y的一个LCS;

3、如果xm != yn,那么zk != yn蕴含Z是X和Y(n-1)的一个LCS。





如何输出lcs?和背包问题一样:考察状态转移方程选择了哪个。

用方向矩阵。


  相关解决方案