输入描述:

输入两个字符串

输出描述:

得到计算结果

abcdefg

abcdef

1

 <?php

 /*

 1、这是一个dp的题目

 2、而且是一个线性dp

 3、f(i)(j)怎么得到f(i)(j)

 4、dp就是刷表，这里明显是刷2维表

 5、f(i)(j)表示什么呢：表示字符串1的前i和字符串2的前就j个的距离，那么最终所有就是f(len(str1))(len(str2))

 6、状态转移方程呢：如果字符串1的最后一个和字符串2的最后一个字符相等，那么f(i)(j)=f(i-1)(j-1)，

 不相等，那么f(i)(j)=min(f(i-1)(j),f(i)(j-1))

 7、想的差不都的时候就直接到excel中根据实例画表即可，不容易出错且清晰快

 */

 while($str1=trim(fgets(STDIN))){

     $str2=trim(fgets(STDIN));

     $len1=strlen($str1);

     $len2=strlen($str2);

     $dp=null;

     for($i=0;$i<=$len2;$i++){

         $dp[]=array_fill(0,intval($len1)+1,0);

     }

     for($i=0;$i<=$len1;$i++){

         $dp[0][$i]=$i;

     }

     for($i=0;$i<=$len2;$i++){

         $dp[$i][0]=$i;

     }

     for($i=1;$i<=$len2;$i++){//行

         for($j=1;$j<=$len1;$j++){//列

             //如果str1[$i-1]在str2:0-$j-1中找到，

             $str1_2=substr($str1,0,$j);

             if(strpos($str1_2,$str2[$i-1])!==false){

                 $dp[$i][$j]=$dp[$i-1][$j-1];

             }else{

                 $dp[$i][$j]=max($dp[$i][$j-1],$dp[$i-1][$j]);

             }

         }

     }

     echo $dp[$len2][$len1].PHP_EOL;

     //print_r($dp);

 }

 ?>