关于edit distance

学了两天dp遇到了一点瓶颈，我看lev distance那个递归公式，觉得它是不是在说每一次delete操作只能处理字符串a最后一位的字符呢，然后变成一个关于无最后一位的子字符串的最优问题, 但是问题定义的delete操作应该是每一次都可以delete任意一个地方的char吧 但那样的话就有太多的可能了，如果只对最后一个char做操作, ，如何理解它的最优性呢

个人认为关键是把大问题拆解成形式一致，规模更小的问题。

每次处理最后一个是为了形成自然的有序序列（从0到i,i始终递增）。事实上如果你愿意的话，每次都处理第0位也是可以的。这在形式上和原来的方法等价。

如果使用双下标来表示一个子串的话，想从中间开始处理应该也可以实现，但那样就没有那么自然了。

子轩不语 发表于 2020/05/22 14:48:50
个人认为关键是把大问题拆解成形式一致，规模更小的问题。

每次处理最后一个是为了形成自然的有序序列（从0到i,i始终递增...

谢了 理解了一些