标签 编辑距离 下的文章

动态规划-用编辑距离解释


前言

什么是编辑距离呢?

我们把“从字符串A到字符串B”的最少操作次数称作编辑距离。操作包含了:插入,删除,替换。比如字符串A = “abc”,字符串B = “abcd”,那么从A到B只需要增加一个字母“d”,所以编辑距离为1;同样的,从B到A只需要删除“d”,所以编辑距离也为1。

状态转移

将需要求解的问题,转移成子问题的过程,叫做状态转移。刻画状态转移的表达式称为状态转移方程式