算法思想之动态规划(五)——最小编辑距离问题

前言

今天我们继续讨论经典的动态规划问题之最小编辑距离问题。

找零钱问题

问题描述

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。例如将"abc"转化为"adc"，c0=5，c1=3，c2=100，最小代价为8。

问题分析

我们先解释下问题描述中为什么最小代价是8。如果插入、删除和修改操作的代价相同，显然，"abc"->"adc"直接将'b'->'d'即可。但是由于多了c0=5，c1=3，c2=100的条件，所以直接进行修改操作其代价为100，显然不是最小代价。最小代价对应的操作应该是使用插入、删除操作代替修改操作——先在'a'与'c'中插入'd'，然后删除'b'，或者先删除'b'，在插入'd'。这样最小代价为8。
其实，该问题实质上是求解的最小编辑距离，只不过对每种操作赋予了权值。假设两字符串A和B的长度分别为和。我们需要构建一个的矩阵，代表的最小代价为。可能你会疑问，为什么是，而不是呢? 观察下面的矩阵，你可能会找到答案。我们需要在两字符串前添加空字符串来得到增加、删除操作所对应的代价作为初始值。

	''	'a'	'd'	'c'
''	0	5	10	15
'a'	3
'b'	6
'c'	9

对于矩阵第0行第0列，代表由，显然代价为0，即;
对于矩阵第0行第1列，代表由，其代价为，即;
对于矩阵第0行第2列，代表由，其代价为，即;
依次类推，。
同样的，对于。
那么当 时，
下面，我们分两种情况进行讨论：
(1) 当 时，可能的操作即最小代价有以下几种情况：

• 不需要进行任何操作，此时最小代价就是的最小代价，即；
• 先，然后增加，此时最小代价为的最小代价 + ，即；
• 先将，然后删除，此时最小代价为的最小代价 + ，即。

此时，;
(2) 当 时，可能的操作即最小代价有以下几种情况：

• 直接将A[i]替换为B[j]，此时最小代价就是的最小代价 + ，即；
• 先，然后增加，此时最小代价为的最小代价 + ，即；
• 先将，然后删除，此时最小代价为的最小代价 + ，即。

此时，;
需要注意的是，当时，需要令，这是因为修改操作可以用增加+删除操作代替，这样的代价比直接进行修改操作的代价要低。问题分析一开始也给出了说明。

代码实现

通过问题分析，可以很容易得用代码实现，下面给出算法的java实现。

public class MinCost {
    public int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
        return core(A, n, B, m, c0, c1, c2);
    }

    public int core(String A, int n, String B, int m, int c0, int c1, int c2) {
        if (A.length() == 0 || B.length() == 0) {
            return 0;
        }
        A = " " + A;
        B = " " + B;
        int[][] dp = new int[n + 1][m + 1];
        // 初始化第0行
        dp[0][0] = 0;
        for (int i = 1; i < m + 1; i++) {
            dp[0][i] = c0 * i;
        }

        // 初始化第0列
        for (int j = 1; j < n + 1; j++) {
            dp[j][0] = c1 * j;
        }

        //update=delete+insert,如果update花费更多就用delete+insert的花费之和替换
        if (c2 >= c0 + c1) {
            c2 = c0 + c1;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    //如果两个字符串中A[i],B[j]的字符都一样的
                    //1.什么都不做就行，0操作
                    int dontChange = dp[i - 1][j - 1];
                    //2.比如由abcd→abcd=abc→abcd+A串删除d
                    int delete = dp[i - 1][j] + c1;
                    //3.比如由abcd→abcd=abcd→abc+B串插入d
                    int insert = dp[i][j - 1] + c0;
                    dp[i][j] = Math.min((Math.min(dontChange, delete)), insert);
                } else {
                    //1. A abcd → B abce = A abc→B abc + (A abcd → B abce, 替换d为e)
                    int replace = dp[i - 1][j - 1] + c2;
                    //2.比如由A abcd→B abce=A abc→B abce+A串删除d
                    int delete = dp[i - 1][j] + c1;
                    //3.比如由A abcd→B abce=A abcd→B abc+B串插入e
                    int insert = dp[i][j - 1] + c0;
                    dp[i][j] = Math.min((Math.min(replace, delete)), insert);
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        MinCost minCost = new MinCost();
        String A = "abc";
        int n = A.length();
        String B = "adc";
        int m = B.length();
        int c0 = 3;
        int c1 = 5;
        int c2 = 3;
        int res = minCost.findMinCost(A, n, B, m, c0, c1, c2);
        System.out.println(res);
    }
}

经典问题

• 算法思想之动态规划(二)——最小路径和问题
• 算法思想之动态规划(三)——找零钱问题
• 算法思想之动态规划(四)——最长公共子序列问题
• 最长上升子序列问题
• 背包问题

未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。