編輯距離：將一個字符串轉(zhuǎn)化成另一個字符串索昂，需要的最少編輯操作次數(shù)（比如增加一個字符、刪除一個字符扩借、替換一個字符）椒惨。編輯距離越大，說明兩個字符串的相似程度越谐弊铩康谆；相反，編輯距離就越小错洁，說明兩個字符串的相似程度越大秉宿。
萊文斯坦距離允許增加、刪除屯碴、替換字符這三個編輯操作描睦。萊文斯坦距離的大小，表示兩個字符串差異的大小

回溯法：如果 a[i] 與 b[j] 匹配导而，遞歸考察 a[i+1] 和 b[j+1]忱叭。
如果 a[i] 與 b[j] 不匹配，那我們有多種處理方式可選：
1.可以刪除 a[i]今艺，然后遞歸考察 a[i+1] 和 b[j]韵丑；
2.可以刪除 b[j]，然后遞歸考察 a[i] 和 b[j+1]虚缎；
3.可以在 a[i] 前面添加一個跟 b[j] 相同的字符撵彻，然后遞歸考察 a[i] 和 b[j+1];
4.可以在 b[j] 前面添加一個跟 a[i] 相同的字符，然后遞歸考察 a[i+1] 和 b[j]实牡；
5.可以將 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;

    // 調(diào)用方式 lwstBT(0, 0, 0);
    public void 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 { // 兩個字符不匹配
            // 刪除a[i]或者b[j]前添加一個字符
            lwstBT(i + 1, j, edist + 1);
            // 刪除b[j]或者a[i]前添加一個字符
            lwstBT(i, j + 1, edist + 1);
            // 將a[i]和b[j]替換為相同字符
            lwstBT(i + 1, j + 1, edist + 1);
        }
    }

動態(tài)規(guī)劃：
如果：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表示求三數(shù)中的最小值总滩。

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) {
            //若相等。差為下標值巡雨。因為從0開始
            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;
    }