动态规划之编辑距离

诶嘿嘿嘿 ->_->

还是那个不认识的同学，还是熟悉的动态规划，只是题目变了，题干如下：

给你两个字符串S1和S2，你可以对S1进行如下操作（插入，删除，替换）来使得S1=S2，求最少的操作数，即莱文斯坦距离。

由特殊的名字（莱文斯坦距离）可以得知，已经有很严谨的推导过程可以得到如下结论

所以，我就不推导了（才不是我懒）

通过以上公式，我们可以得到以下关键代码

int minDistance1(char word1[], char word2[]) {
    int dp[1000][1000];
    for (int i = 0; i <= strlen(word1); i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i <= strlen(word2); i++) {
        dp[0][i] = i;
    }
    int cost;
    for (int i = 1; i <= strlen(word1); i++) {
        for (int j = 1; j <= strlen(word2); j++) {
            if (word1[i - 1] == word2[j - 1]) {
                cost = 0;
            } else {
                cost = 1;
            }
            dp[i][j] = min1(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
        }
    }
    return dp[strlen(word1)][strlen(word2)];
}

最终代码

#include<iostream>
int min(int a,int b)
{
    return a<b?a:b;
}
int min1(int x, int y, int z) {
    return min(x, min(y, z));
}
int minDistance1(char word1[], char word2[]) {
    int dp[1000][1000];
    //初始化DP数组
    for (int i = 0; i <= strlen(word1); i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i <= strlen(word2); i++) {
        dp[0][i] = i;
    }
    int cost;
    for (int i = 1; i <= strlen(word1); i++) {
        for (int j = 1; j <= strlen(word2); j++) {
            if (word1[i - 1] == word2[j - 1]) {
                cost = 0;
            } else {
                cost = 1;
            }
            dp[i][j] = min1(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
        }
    }
    return dp[strlen(word1)][strlen(word2)];
}


int main(){
    char a[100],b[100];
    scanf("%s %s",a,b);
    int ans;
    ans=minDistance1(a, b);
    printf("%d\n",ans);
}