编辑距离

编辑距离指在有限编辑条件下（增加，删除，替换），将一个字符串变换成另一个字符串所需的最小操作次数。语音中用到编辑距离的地方还是蛮多的，比如对CTC的预测进行评估的时候，就可以采用编辑距离。

一开始接触这个问题还是比较难和动态规划结合起来的，但是指明DP之后，转移方程还是很好写出来的，定义$D_{i, j}$为子串$A_{0 \to i}$和$B_{0 \to j}$的编辑距离，显然，状态$(i, j)$可以退化为三个状态：$(i - 1, j - 1), (i - 1, j), (i, j - 1)$，下面就是指出三个子状态和目标状态的关系。

• 若$A[i] = B[j]$，则$D_{i, j} = D_{i - 1, j - 1}$，如果不相等，替换其中一个使它们相等，引入一步操作。
• 删除$A[i]$或者$B[j]$，引入一步操作。

反过来考虑，子状态转移到目标状态的话，删除逻辑改为增加逻辑即可。程序的话，习惯记忆化搜索，自上而下的逻辑。边界条件：$D_{0, i} = D_{i, 0} = i$，代码逻辑如下：

int EditDist(char *a, char *b, int i, int j) {
    if (i + j < 0)
        return 0;
    if (i == 0 || j == 0)
        return dis[i][j] = (i == 0 ? j: i);
    if (dis[i][j] >= 0)
        return dis[i][j];
    if (a[i] == b[j])
        return dis[i][j] = EditDist(a, b, i - 1, j - 1);
    else
        return dis[i][j] = min(
                    EditDist(a, b, i - 1, j - 1),
                    EditDist(a, b, i, j - 1),
                    EditDist(a, b, i - 1, j)
                ) + 1;
}