带你读《图解算法小抄》二十四、字符串（1）https://developer.aliyun.com/article/1347819?groupCode=tech_library
4）动态规划方法解释
让我们以查找字符串 ME 和 MY 之间的最小编辑距离为例。直观上，您已经知道这里的最小编辑距离是 1，即将 E 替换为 Y。但是，让我们试图将其正式化为算法形式，以便能够处理更复杂的示例，如将 Saturday 转换为 Sunday。
为了将上述数学公式应用于 ME → MY 转换，我们需要事先知道 ME → M、M → MY 和 M → M 转换的最小编辑距离。然后，我们需要选择其中最小的一个，并在最后一个字母 E → Y 上增加一次操作。因此，ME → MY 转换的最小编辑距离是基于三个先前可能的转换计算得出的。
为了进一步解释这一点，我们来绘制下面的矩阵：
Levenshtein 矩阵
- 单元格 (0:1) 包含红色数字 1。这意味着我们需要 1 次操作将 M 转换为空字符串。这就是为什么这个数字是红色的。
- 单元格 (0:2) 包含红色数字 2。这意味着我们需要 2 次操作将 ME 转换为空字符串。这是通过删除 E 和 M 完成的。
- 单元格 (1:0) 包含绿色数字 1。这意味着我们需要 1 次操作将空字符串转换为 M。这是通过插入 M 完成的。这就是为什么这个数字是绿色的。
- 单元格 (2:0) 包含绿色数字 2。这意味着我们需要 2 次操作将空字符串转换为 MY。这是通过插入 Y 和 M 完成的。
- 单元格 (1:1)包含数字 0。这意味着将 M 转换为 M 不需要任何操作。
- 单元格 (1:2) 包含红色数字 1。这意味着我们需要 1 次操作将 ME 转换为 M。这是通过删除 E 完成的。
- 以此类推...
对于我们这样小的矩阵（只有 3x3），看起来很简单。但是，您可以从中找到可以应用于计算更大矩阵（例如，用于 Saturday → Sunday 转换的 9x7 矩阵）的基本概念。
根据上述公式，您只需要找到相邻单元格 (i-1:j)、(i-1:j-1) 和 (i:j-1) 中的最小值，然后在行 i 的字母和列 j 的字母不同的情况下加 1。
您可以清楚地看到问题的递归性质。
让我们为这个问题绘制一个决策图。
您可以在图片中看到一些带有红色标记的重叠子问题。而且没有办法减少操作数并使其少于公式中那三个相邻单元格中的最小值。
带你读《图解算法小抄》二十四、字符串（3）https://developer.aliyun.com/article/1347817
