1. 最少改动完成字符串变化

最少改动完成字符串变化从$a -> $b，每步操作只能插入，删除，修改一个字符

1.1. 分析

1.1.1 发现

由于每次的操作功能，当前字符串，变成下一个字符串，多一个字符时：

1. 如果是一样的字符，则本次变化不需要操作
2. 否则需要（操作是：插入，删除，修改）步骤数 +1
3. 此时整个问题的规模缩小为：到达步骤2时需要的最小步骤数了（此时状态记为x），以此类推…

1.1.2 解法

动态规划 ：

1. 遍历$a ，从1 - strlen($a)字符变成，$b从1 - strlen($b)时的最小步数
2. 得到一个字符变化图
3. 得到递推公式：

用 dp[i][j] 表示字符串$a从i长度变成字符串$b的j长度时的最小移动步骤

(str1[i] === str2[j])   =>  dp[i][j] = dp[i-1][j-1]
(str1[i] !== str2[j])      =>  dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

1.1.3 优化

当边界条件出现：

1. 存在空字符串时 ：任何dp[0][j] = j，dp[i][0] = i

   1.2 具体代码实现：

   function df($str1, $str2)
   {
   $str1 = '#'.$str1;
   $str2 = '#'.$str2;
   
   $dp = [];
   for ($i = 0; $i < strlen($str1); $i++) {
     $dp[$i][0] = $i;
   }
   for ($i = 0; $i < strlen($str2); $i++) {
     $dp[0][$i] = $i;
   }
   
   for ($i = 1; $i < strlen($str1); $i++) {
     for ($j = 1; $j < strlen($str2); $j++) {
         if ($str1[$i] == $str2[$j]) {
             $dp[$i][$j] = $dp[$i - 1][$j - 1];
         } else {
             $dp[$i][$j] = min($dp[$i - 1][$j - 1], min($dp[$i][$j - 1], $dp[$i - 1][$j])) + 1;
         }
     }
   }
   
   return $dp;
   }