搜索引擎中的自动纠错和提示功能，是对用户输入字符串，计算其相似字符串。
比如mouse就是用户输入mouuse的相似字符串。
一个字符串有哪些相似字符串，无非是把该字符串进行一系列可能的变形编辑。比如把某个字母删掉，或增加一个字母，或替换该字母
最后看变形后的单词，是否是一个合法单词。如果是，则给用户提示。

原始单词或字符变形到一个合法字符串的步数，称为这两个单词之间的编辑距离。

但一个单词随着长度增加，其对应的合法单词，编辑距离计算将会很多。不可取。

所以需要最优解，找出用户输入词，编辑距离最小的目标词即可

#include <iostream>

using namespace std;
void levenshteinDis(const char* str1, const char* str2, int m, int n,
                    int i, int j, int edist, int &mind) {
    if (i == m || j == n) {
        if (i < m) edist += (m-i);
        if (j < n) edist += (n-j);
        if (edist < mind) mind = edist;
        return;
    }

    if (str1[i] == str2[j]) {
        levenshteinDis(str1, str2, m, n, i+1, j+1, edist, mind);
    } else {
        // 删除或增加
        levenshteinDis(str1, str2, m, n, i+1, j, edist+1, mind);
        levenshteinDis(str1, str2, m, n, i, j+1, edist+1, mind);
        // 替换操作
        levenshteinDis(str1, str2, m, n, i+1, j+1, edist+1, mind);
    }
}

int levenshteinDis(const char* a, const char* b, int m, int n) {
    int mind = 0xfffffff;
    levenshteinDis(a, b, m, n, 0, 0, 0, mind);
    return mind;
}

/*
 * 状态转移方程
 * 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)
 * 2.当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))
 */
int levenshteinDisDP(const char* a, const char* b, int m, int n) {
    // 初始化dp数组
    int dp[m][n];
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = 0;
        }
    }

    // 初始化第0列
    for (int i = 0; i < m; ++i) {
        if (a[i] == b[0]) dp[i][0] = i;
        else if (i != 0) dp[i][0] = dp[i-1][0] + 1;
        else dp[i][0] = 1;
    }

    // 初始化第0行
    for (int i = 0; i < n; ++i) {
        if (a[0] == b[i]) dp[0][i] = i;
        else if (i > 0) dp[0][i] = dp[0][i-1] + 1;
        else dp[0][i] = 1;
    }

    // 填表余下部分
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1,
                    a[i] == b[j] ? dp[i-1][j-1]:dp[i-1][j-1]+1);
        }
    }
    return dp[m-1][n-1];
}

编辑距离解析，其实看看下面这个结合图会好理解一点，其实就是下一个结果基于上一个结果的一种情况去进行加0还是加0，老师说的真的一头雾水，大家可以参考一下
解析：
i相当于第几行，j相当于第几列
1.如果i或者j=0就是edit(i,j)=j或者i；
2.左(i-1,j)，上(i,j-1)，左上(i-1,j-1)相当于前一个子集可能出现的三种情况的下求最小值，其中左+1，上+1，右上(如果当前i=j，则+0，不等则+1)，，求这三者的最小值例如：左=1，左上=0，上=1则 edit(左)=1+1=2，如果当前格子对应行列的数据相等则edit(左上)=0+0=0，否则edit(左上)=0+1=1，edit(上)=1+1=2,所以结果就是edit(i,j)=min{edit(左),edit(左上),edit(上)}

如果词库中的词条数量很大，利用编辑距离来匹配词条的相似度效率会比较低，因为编辑距离的计算是逐个字符进行匹配扫描的，做相似度匹配时需要选出编辑距离最短的那个词条，这样就需要扫描整个词库，才能获得具有最短距离的词条。
       我个人的优化方案：预先把每个词条的前缀全部剥离出来，某些词条的前缀可能是重复的，建立前缀与词条的一对多关系，利用哈希算法，得到每个前缀的哈希值，同时把各个前缀存贮于哈希表中，哈希表中除了存贮前缀哈希值，同时还存贮该前缀属于哪个词条，即词条的索引号，这样每次查询时，先把要查询的词条按相同的哈希算法，算出哈希值，再根据哈希值，得到该前缀所属的所有词条，这样就缩小了查询范围，然后再计算每个词条和被查询的词条的编辑距离，得到相近的词。
以上是我个人的一点浮浅理解，请老师指正。

本篇所得：动态规划 为寻找的最优解，它只关心 最优的一个解，其他的不会再考虑，比如求解 数组的最大 和最小值，一般只有一个（可能有重复的最值，但最值是相等的）。

工作和生活中，我们一般把大问题分解为小问题，再把小问题 分解为容易解答的问题，动态规划 就是在 容易解答的问题中选择最优解。

黄老师 在文中提到：搜索引擎输入的搜索词的查询和推荐，就是对 缺失和错误的字符串进行操作，比如我们输入错误的字符串A，和正确的字符串B，需要把字符串A改到B，需要把字符串 分解到字符 的小问题，然后进行‘增、删、改’等操作，这里运用 动态规划 寻找最优解，不需要使用排列 这么复杂的方法 因为排列计算消耗的时间会很长，运用动态规划 很节能。

今天所得：解决问题的方法 （1）不断的分解问题，把大问题分解为小问题，把小问题 再分解...直至到可以解答的问题;（2）使用动态规划 求解 小问题的 最优解。

回答老师的问题：用编辑距离对字符串状态转移资源消耗的标记，会浪费很多 内存和运算资源，可以把 字符串 再分割成字符，把 二个字符串的不同的字符 掏出来，再用编辑距离 处理，应该会更快一下、占用资源也少一些，老师是否同意，也期待 黄老师的指正。

老师 可以用 斐波那契数列 来说明 动态规划的问题，更让我们易理解。

看懵了。下一节表格下面说明，三种编辑距离分别是：替换、插入和删除字符。
本节：三种编辑距离 2,2,0。最后一个是替换。

替换操作理解，插入和删除不理解。老师帮忙分析下。
一种情况：
A字符为：m B字符为：mo

第二种情况：
A字符为：mo B字符为：mo

黄老师，
我们先考虑最简单的情况。假设字符串 A 和 B 都是空字符串，那么很明显这个时候编辑距离就是 0。如果 A 增加一个字符 a1，B 保持不动，编辑距离就增加 1。同样，如果 B 增加一个字符 b1，A 保持不动，编辑距离增加 1。但是，如果 A 和 B 有一个字符，那么问题就有点复杂了，我们可以细分为以下几种情况。(这个可以理解。)
我们先来看插入字符的情况。A 字符串是 a1 的时候，B 空串增加一个字符变为 b1；或者 B 字符串为 b1 的时候，A 空串增加一个字符变为 a1。很明显，这种情况下，编辑距离都要增加 1。(这个也可以理解。)
我们再来看替换字符的情况。当 A 和 B 都是空串的时候，同时增加一个字符。如果要加入的字符 a1 和 b1 不相等，表示 A 和 B 之间转化的时候需要替换字符，那么编辑距离就是加 1；如果 a1 和 b1 相等，无需替换，那么编辑距离不变。(这个有点懵啊)
最后，我们取上述三种情况中编辑距离的最小值作为当前的编辑距离。注意，这里我们只需要保留这个最小的值，而舍弃其他更大的值。这是为什么呢？因为编辑距离随着字符串的增长，是单调递增的。所以，要求最终的最小值，必须要保证对于每个子串，都取得了最小值。有了这点，之后我们就可以使用迭代的方式，一步步推导下去，直到两个字符串结束比较。(这里也有点懵)