最长公共子序列php 动态规划(最长公共子序列LCS)

概念

求解决策过程最优化的结果 (可能有多个)

把多阶段过程转化为一系列单阶段过程,利用各阶段之间的关系,逐个求解

计算过程中会把结果都记录下,最终结果在记录中找到.

举例

求两个字符串的最长公共子序列

字符串如下

x : bdcaba 纵坐标

y : abcbdab 横坐标

矩阵展示

x/y

a

b

c

b

d

a

b

b

0

1

0

1

0

0

1

d

0

1

1

1

2

2

2

c

0

1

2

2

2

2

2

a

1

1

2

2

2

3

3

b

0

2

2

3

3

3

4

a

1

2

2

3

3

4

4

填表公式:

image.png

php代码实现

/**

* php 实现动态规划 最长公共子序列LCS

*/

class LcsTest

{

private $xa;

private $ya;

private $max;

private $wayCount;

private $matrix;

private $indexs;

private $results;

private $moves;

public function lcs($x,$y){

//属性重置

$this->max = 0;

$this->wayCount = 0;

$this->matrix = [];

$this->indexs = [];

$this->results = [];

$this->moves = [];

//字符串拆分为数组

$this->xa = str_split($x);

$this->ya = str_split($y);

//1、生成矩阵

$this->createMatrix();

//1、输出矩阵页面到屏幕并且记录最优解的下标

$this->writeMatrix();

//3、获取所有可能走向

foreach($this->indexs as $index){

$data = $this->getWay($index['i'],$index['j'],$this->wayCount);

$this->wayCount++;

}

//4、输出结果

$this->writeResults();

}

/**

* 从后向前寻找可能走向

* @param integer $xlen

* @param integer $ylen

* @param integer $n

* @return

*/

private function getWay($xlen,$ylen,$n){

isset($this->results[$n]) || $this->results[$n] = [];

isset($this->moves[$n]) || $this->moves[$n] = [];

while ($xlen>=0&&$ylen>=0) {

if($this->xa[$xlen]==$this->ya[$ylen]){

//移动位置过程

$this->moves[$n][] = sprintf('%s:%s:%s:true',$this->xa[$xlen],$this->ya[$ylen],$this->matrix[$xlen][$ylen]);

//移动点数据

$this->results[$n][] = $this->xa[$xlen];

$xlen--;

$ylen--;

}

else{

//移动位置过程

$this->moves[$n][] = sprintf('%s:%s:%s:false',$this->xa[$xlen],$this->ya[$ylen],$this->matrix[$xlen][$ylen]);

if($this->matrix[$xlen-1][$ylen]>$this->matrix[$xlen][$ylen-1]){

$xlen--;

}

//如果相等证明2条路可走需要进行扩散

else if($this->matrix[$xlen-1][$ylen]==$this->matrix[$xlen][$ylen-1]){

$this->wayCount++;

//新开辟一条

$this->results[$this->wayCount] = $this->results[$n];

$this->getWay($xlen,$ylen-1,$this->wayCount);

//之前的继续走

$this->getWay($xlen-1,$ylen,$n);

break;

}

else{

$ylen--;

}

}

}

}

/**

* 生成矩阵

* @return

*/

private function createMatrix(){

foreach ($this->xa as $xi => $xv) {

foreach ($this->ya as $yi => $yv) {

if($xv==$yv){

$this->matrix[$xi][$yi] = $xi==0||$yi==0?1:$this->matrix[$xi-1][$yi-1]+1;

}

else {

$this->matrix[$xi][$yi] = $xi==0||$yi==0?0:max([$this->matrix[$xi-1][$yi],$this->matrix[$xi][$yi-1]]);

}

if($this->matrix[$xi][$yi]>$this->max){

$this->max = $this->matrix[$xi][$yi];

}

}

}

}

/**

* 输出矩阵到屏幕方便分析并且记录最优解所在坐标

* @return

*/

private function writeMatrix(){

echo '----------矩阵列表--------------',PHP_EOL,PHP_EOL;

echo " ",implode(" ",$this->ya),PHP_EOL;

foreach ($this->matrix as $ri => $rv) {

echo $this->xa[$ri]," ";

foreach ($rv as $rvi => $rvv) {

//取出所有的最优解

if($rvv == $this->max){

$this->indexs[] = [

'i' => $ri,

'j' => $rvi,

];

}

echo $rvv," ";

}

echo PHP_EOL;

}

}

/**

* 输出结果到屏幕方便对比

* @return

*/

private function writeResults(){

echo '----------移动过程--------------',PHP_EOL;

echo '格式 纵坐标:横坐标:层级:是否符合',PHP_EOL,PHP_EOL;

foreach ($this->moves as $move) {

if(empty($move)){

continue;

}

//输出从后向前找的过程 纵坐标：横坐标 : 层级

echo implode(" -> ",$move),PHP_EOL;

}

echo '----------最终结果--------',PHP_EOL;

foreach ($this->results as $result) {

if(empty($result)){

continue;

}

//得到的是逆序结果 反转数组后输出

$data = array_reverse($result);

echo implode(" ",$data),PHP_EOL;

}

}

}

$test = new LcsTest();

$test->lcs("bdcaba","abcbdab");

执行结果

----------矩阵列表--------------

a b c b d a b

b 0 1 0 1 0 0 1

d 0 1 1 1 2 2 2

c 0 1 2 2 2 2 2

a 1 1 2 2 2 3 3

b 0 2 2 3 3 3 4

a 1 2 2 3 3 4 4

----------移动过程--------------

格式 纵坐标:横坐标:层级:是否符合

b:b:4:true -> a:a:3:true -> c:d:2:false -> d:d:2:true -> b:b:1:true

c:b:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true

a:a:4:true -> b:d:3:false -> b:b:3:true -> a:c:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true

a:b:4:false -> b:b:4:true -> a:a:3:true -> c:d:2:false -> d:d:2:true -> b:b:1:true

a:a:4:true -> b:d:3:false -> b:b:3:true -> a:c:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true

c:b:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true

----------最终结果--------

b d a b

b c a b

b c b a

b d a b

b c b a

b c a b

总结分析

第一步主要生成列表

第一步主要获取最优解的最大长度 并且符合长度的下标都取出

第三步 根据所有最优解下标从后向左前方向一步一步走,哪里大走向哪里

重点部分 如果值相等说明出现2种情况 需要扩散第二条路 无限扩散

最终得到所有情况 输出即可