51Nod 1183 编辑距离

本文主要是介绍51Nod 1183 编辑距离，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：51Nod 1183 编辑距离

题目大意：

题解：
设\(dp[i][j]\)为字符串\(A\)的前\(i\)个字符变成字符串\(B\)的前\(j\)个字符需要的最小操作数。
若字符串\(A\)的第\(i\)个字符与字符串\(B\)的第\(j\)个字符相等，则问题变成将字符串\(A\)的前\(i-1\)个字符变成字符串\(B\)的前\(j-1\)个字符；否则，执行替换、插入或删去字符操作，操作数加一。
状态转移方程为：

#include <iostream>
#include <string>
using namespace std;

int dp[1010][1010];
string a, b;

int main() {
    cin >> a >> b;
    int lena = a.length(), lenb = b.length();
    if (!lena) {
        cout << lenb;
    } else if (!lenb) {
        cout << lena;
    } else {
        for (int i = 0; i <= lena; ++i) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= lenb; ++j) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= lena; ++i) {
            for (int j = 1; j <= lenb; ++j) {
                dp[i][j] = min(dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]), min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
        cout << dp[lena][lenb];
    }
    return 0;
}

这篇关于51Nod 1183 编辑距离的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！