题解 | #最小编辑代价#

最小编辑代价

题意分析：

题解一（动态规划）：

最优子结构：设输入序列为 $X[0...m - 1]$ 和 $Y [0...n-1]$ ，长度分别为m和n。
假设 $dp(X[i],Y[j])$ 为两个序列 $X$ 和 $Y$ 在位置 $i$ 和位置 $j$ 的最短编辑数。
如果两个序列的最后一个字符相等（或 $X[m-1] == Y[n-1]$ )，则

$dp(X[m-1],Y[n-1]) =dp(X[m-2],Y[n-2])$

如果两个序列的最后一个字符不相等( $X[m-1]!= Y[n-2]$ )，则有三种选择：取三种选择最小操作数

$dp(X[m-1],Y[n-1])= min(dp(X[m-2],Y[n-1]),dp(X[m-1]),Y[n-2]),dp(X[m-2],Y[n-2]))$

如有序列“AGAB” 和“GXAYB”。

它们最后一个字符相等
$dp(“AGAB”, “GXAYB”) = dp(“AGA”, “GXAY”)$
再考虑“AGA” 和“GXAY“，他们最后一个字符并不相等。
$dp(“AGA”,“GXAY”) =min(dp(“AG”, “GXAY”),dp(“AGA”, “GXA”),dp("AG","GXA"))$
按照上面这种递归，数据量大就会超时，自底向上书写代码。
当其中一个序列长度为0时，编辑距离明显是到达他的长度。

当当前位置 $i,j$ 字符相等时候，编辑距离 $dp[i][j]=dp[i-1][j-1]$

当当前位置 $i,j$ 字符不相等时候，编辑距离 $dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])$

如图所示，计算过程

图所示为子顶向下的计算过程。

int minEditCost(string str1, string str2, int ic, int dc, int rc) {
    int m = str1.length(),n = str2.length();
    int dp[m+1][n+1];
    for(int i=0;i<=m;++i)
    {
        for(int j=0;j<=n;++j)
        {
            if(i==0) {

                dp[i][j] =j*ic;
            }
            else if(j==0){
                dp[i][j]=i*dc;
            }
            else if(str1[i-1]==str2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }
            else {
                dp[i][j] = min({dp[i-1][j]+dc,dp[i-1][j-1]+rc,dp[i][j-1]+ic});
            }
        }
    }
    return dp[m][n];
}

时间复杂度： $O(mn)$ ，mn分别为两个字符串的长度

空间复杂度： $O(mn)$