给定两个字符串 s1 和 s2，计算出将 s1 转换成 s2 所使用的最少操作数。 你可以对一个字符串进行如下三种操作： 1、插入一个字符 2、删除一个字符 3、替换一个字符

示例 输入：s1 = “horse”，s2 = “ros” 输出：3 解释： horse -> rorse （将 h 替换成 r） rorse -> rose（删除r） rose -> ros（删除e）

使用动态规划解题

动态规划解题框架： 1、动态转移方程 2、重叠子问题 3、最优子结构 4、状态压缩 解决两个字符串的动态规划问题，一般都是用两个指针i、j分别指向两个字符串的尾部，然后一步一步向前移动指针，缩小问题的规模。

找出 状态/选择

定义dp函数：
**
dp(i,j) -> Int：返回字符串 s1[0,1,...i] 和s2[0,1,...j]的最短编辑距离，每次指针移动时，对应四种不同选择：

  • 不变(s1、s2对应位置的字符本身就相同)，此时，dp(i,j)等价于dp(i-1,j-1)
  • 插入一个字符，此时，dp(i,j)等价于dp(i,j-1) + 1
  • 删除一个字符，此时，dp(i,j)等价于dp(i-1,j) + 1
  • 替换一个字符，此时，dp(i,j)等价于dp(i-1,j-1) + 1

base case
**
当 i 或者 j 为 -1 时，表明 s1 或 s2 遍历完成，此时直接返回另外一个字符剩余的长度即可。

解决重叠子问题

对于子问题 dp(i-1, j-1)，原问题dp(i,j)可分别通过以下两个流程得到：

  • 先插入再删除
  • 替换字符

存在重叠子问题，故可通过dp table或者备忘录解决重叠子问题。

状态压缩

TODO