> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0072_edit_distance/slt.md).

# 思路1 dp

D\[i]\[j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。

当word\[i] == word\[j]时， d\[i]\[j] = d\[i-1]\[j-1]，因为新加上的字符相等，无需编辑

当word\[i] != word\[j]时，有三种情况

dp\[i]\[j] = min(dp\[i-1]\[j-1], dp\[i-1]\[j], dp\[i]\[j-1]) + 1

* dp\[i-1]\[j-1]到dp\[i]\[j]需要进行一次替换。因为在i-1和j-1的时候，两个字符串已经完成编辑相等了。两个words各加一个新字符，再进行一次转换就行了
* dp\[i-1]\[j]到dp\[i]\[j]，需要删除一个字符。i-1和j已经是相等的了，word1再新加一个字符。把这个新加的字符删掉还是相等
* dp\[i]\[j-1]到dp\[i]\[j]，需要插入一个字符。因为word2新加了一个字符，word1也需要插入新加的字符。

另外有编辑情况dp\[0]\[j] = j, dp\[i]\[0] = i。表示空字符串和非空字符串之间的转换