动态规划实战

量化两个字符串之间的相似程度-编辑距离(Edit Distance)
编辑距离指的是，将一个字符串转化成另一个字符串，需要的最少编辑操作次数（增加一个字符、删除一个字符、替换一个字符）。编辑距离越大说明两个字符串的相似程度越小；相反编辑距离越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是0。

根据所包含的编辑操作种类的不同，编辑距离有多种不同的计算方式：
莱文斯坦距离，允许增加、删除、替换字符，表示两个字符串差异的大小；
最长公共子串长度，允许增加、删除字符，表示两个字符串相似程度的大小。

莱文斯坦距离

把一个字符串变成另一个字符串，需要的最少编辑次数。
整个求解过程，涉及多个决策阶段，需要依次考察一个字符串中的每个字符，跟另一个字符串中的字符是否匹配，匹配与不匹配分别对应不同的处理方式。符合多阶段决策最优解模型（贪心、回溯、动态规划）。

回溯算法-递归处理
如果a[i]与b[j]匹配，递归考察a[i+1]和b[j+1]。
如果a[i]与b[j]不匹配：

删除a[i]，递归考察a[i+1]和b[j]；
删除b[j]，递归考察a[i]和b[j+1]；
在a[i]前面添加一个跟b[j]相同的字符，然后递归考察a[i]和b[j+1]；
在b[j]前面添加一个跟a[i]相同的字符，然后递归考察a[i+1]和b[j]；
将a[i]替换成b[j]，或者将b[j]替换成a[i]，然后递归考察a[i+1]和b[j+1]。

莱文斯坦距离回溯算法

private char[] a = "mitcmu".toCharArray();
private char[] b = "mtacnu".toCharArray();
private int n = 6;
private int m = 6;
private int minDist = Integer.MAX_VALUE;
public lwstBT(int i, int j, int edist) {
    if(i == n || j == m) {
        if(i < n) edist += (n-i);
        if(j < m) edist += (m-j);
        if(edist < minDist) minDist = edist;
        return;
    }
    if(a[i] == b[j]) {//两个字符匹配
        lwstBT(i+1, j+1, edist);
    } else {//两个字符不匹配
        lwstBT(i+1, j, edist+1);//删除a[i]或者b[j]前添加一个字符
        lwstBT(i, j+1, edist+1);//删除b[j]或者a[i]前添加一个字符
        lwstBT(i+1, j+1, edist+1);//将a[i]和b[j]替换为相同字符
    }
}

根据回溯算法的代码实现，可以画出递归树，看是否存在重复子问题。
如果存在重复子问题，可以考虑是否用动态规划来解决；
如果不存在重复子问题，那回溯算法就是最好的解决方法。
在递归树中，每个节点代表一个状态，状态包含三个变量(i,j,edist)，其中edist表示处理a[i]和b[j]时，已经执行的编辑操作的次数。
在递归树中，(i,j)两个变量重复的节点很多。
对于(i,j)相同的节点，只需要保留edist最小的，继续递归处理就可以了，剩下的节点都可以舍弃。所以状态就从(i,j,edist)变成了(i,j,min_edist)，其中min_edist表示处理到a[i]和b[j]已经执行的最小编辑次数。
状态(i,j)可能从(i-1,j)、(i,j-1)，(i-1,j-1)三个状态中的任意一个转移过来。
尝试将状态转移的过程用公式写出来-状态转移方程

如果:a[i]!=b[j],那么:min_edist(i,j)就等于:
min(min_edist(i-1,j)+1,min_edist(i,j-1)+1,min_edist(i-1,j-1)+1)

如果:a[i]=b[j],那么:min_edist(i,j)就等于:
min(min_edist(i-1,j)+1,min_edist(i,j-1)+1,min_edist(i-1,j-1))
min表示求三数中的最小值
了解状态与状态之间的递推关系，画出一个二维状态表，按行依次来填充状态表中的每个值。

根据状态转移方程和填表过程，翻译成代码：

莱文斯坦距离动态规划

public int lwstDP(char[] a, int n, char[] b, int m) {
    int[][] minDist = new int[n][m];
    //初始化第0行：a[0...0]与b[0...j]的编辑距离
    for(int j=0; j<m; ++j) {
        if(a[0] == b[j]) minDist[0][j] = j;
        else if(j != 0) minDist[0][j] = minDist[0][j-1] +1;
        else minDist[0][j] = 1;
    }
    //初始化第0列：a[0...i]与b[0...0]的编辑距离
    for(int i =0; i < n; ++i) {
        if(a[i] == b[0]) minDist[i][0] = i;
        else if(i != 0) minDist[i][0] = minDist[i-1][0] + 1;
        else minDist[i][0] = 1;
    }
    //按行填表
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            if(a[i] == b[j]) minDist[i][j] = min(minDist[i-1][j] + 1, minDist[i][j-1] + 1, minDist[i-1][j-1]);
            else minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
        }
    }
    return minDist[n-1][m-1];
}
private int min(int x, int y, int z) {
    int minv = Integer.MAX_VALUE;
    if(x < minv) minv = x;
    if(y < minv) minv = y;
    if(z < minv) minv = z;
    return minv;
}

最长公共子串长度

解决思路类似莱文斯坦距离
每个状态包括三个变量(i,j,max_lcs)，max_lcs表示a[0…i]和b[0…j]的最长公共子串长度。
从a[0]和b[0]开始，依次考察两个字符串中的字符是否匹配。

如果a[i]与b[j]互相匹配，将最大公共子串长度加一，并且继续考察a[i+1]和b[j+1]。
如果a[i]和b[j]不匹配，最长公共子串长度不变，解决思路：
- 删除a[i]，或者在b[j]前面加上一个字符a[i]，然后继续考察a[i+1]和b[j]；
- 删除b[j]，或者在a[i]前面加上一个字符b[j]，然后继续考察a[i]和b[j+1]。

求a[0…i]和b[0…j]的最长公共长度max_lcs[i,j]，只能通过下边三个状态转移过来：

(i-1, j-1, max_lcs)，其中max_lcs表示a[0…i-1]和b[0…j-1]的最长公共子串长度；
(i-1, j, max_lcs)，其中max_lcs表示a[0…i-1]和b[0…j]的最长公共子串长度；
(i, j-1, max_lcs)，其中max_lcs表示a[0…i]和b[0…j-1]的最长公共子串长度。

状态转移方程：

如果：a[i]==b[j]，那么：max_lcs(i,j)就等于：
max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1));
aba与a的最长公共子串是1不是2；max_lcs(i-1, j)与max_lcs(i, j-1)不需要+1。

如果：a[i]!=b{j}，那么：max_lcs(i,j)就等于：
max(max_lcs(i-1,j-1), max_lcs(i-1, j), max(i, j-1));
max表示求三个数中的最大值；

代码实现：

最长公共子串长度动态规划

public int lcs(char[] a, int n ,char[] b, int m) {
    int[][] maxlcs = new int[n][m];  
    for(int j = 0; j < m; ++j) {
        if(a[0] == b[j]) maxlcs[0][j] = 1;
        else if(j != 0) maxlcs[0][j] = maxlcs[0][j-1];
        else maxlcs[0][j] = 0;
    }
    for(int i = 0; i < n; ++i) {
        if(a[i] == b[0]) maxlcs[i][0] = 1;
        else if(i != 0) maxlcs[i][0] = maxlcs[i-1][0];
        else maxlcs[i][0] = 0;
    }
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            if(a[i] == b[j])
                maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
            else 
                maxlcs[i][j] = max(maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
        }
    }
    return maxlcs[n-1][m-1];
}
private int max(int x, int y, int z) {
    int maxv = Integer.MIN_VALUE;
    if(x > maxv) maxv = x;
    if(y > maxv) maxv = y;
    if(z > maxv) maxv = z;
    return maxv; 
}

搜索引擎纠错优化

纠错效果优化：

取编辑距离最小的TOP10，加上其他参数（如搜索热门程度），决策选择哪个单词作为拼写纠错单词。。
多种编辑距离计算方法，求交集，用交集的结果继续优化处理。
统计用户的搜索日志，得到最常被拼错的单词列表，以及对应的拼写正确的单词。搜索引擎找到对应直接返回。
引入个性化因素，针对每个用户，维护其特有的搜索喜好-常用搜索关键词，当用户输入错误的单词的时候，首先在该用户常用的搜索关键词中，计算编辑距离，查找编辑距离最小的单词。

纠错性能优化：

针对纠错功能的TPS不高，可部署多台机器，每台机器运行一个独立的纠错功能。当有一个纠错请求的时候，通过负载均衡，分配到其中一台机器，开计算编辑距离，得到纠错单词。
针对纠错系统的响应时间太长，可将纠错的词库分割到多台机器。当有一个纠错请求的时候，将拼写错误的单词同时发送到多台机器上并行处理，分别得到编辑距离最小的单词，然后再对比合并，最终决定一个最优的纠错单词。