编辑距离

核心顿悟突破口

二维编辑距离可以压缩到一维。dp[j] 表示处理当前行之前或当前行的状态，prev 保存左上角状态；当两个字符不同，就从删除、插入、替换三种操作中取最小值。