本文主要是介绍NOJ 1224 编辑距离问题 (线性dp 分类)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
编辑距离问题
Description
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。
对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。Input
输入数的第一行是字符串A，文件的第二行是字符串B。
Output
输出编辑距离d(A,B)的第1行中。
Sample Input
fxpimu
xwrs
Sample Output
5
题目链接 :http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1224
题目分析 :设dp[i][j]为A从a0...ai变到B从b0...bj的最小操作次数，然后每次对三种操作每次取最小得方案，初时时刻dp[0][j] = j和dp[i][0]＝i因为只需添加或删除对应的字符数即可，接下来删除为dp[i-1][j] + 1，插入为dp[i][j-1] + 1，改变为dp[i-1][j-1] + (A[i-1] == B[j-1] ? 0 : 1)，三种情况下取最小解即为当前最优状态，一直推到dp[strlen(A)][strlen(B)]即为最终答案，这里将A变为B和将B变为A的最优解其实是一样的
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1800;
int dp[MAX][MAX];
char A[MAX], B[MAX];int min3(int a, int b, int c)
{return min(a, min(b, c));
}void cal(int len1, int len2)
{for(int i = 0; i <= len1; i++)dp[i][0] = i;for(int j = 0; j <= len2; j++)dp[0][j] = j;for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++)dp[i][j] = min3(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (A[i-1] == B[j-1] ? 0 : 1));printf("%d\n", dp[len1][len2]);
}int main()
{while(gets(A) && gets(B))cal(strlen(A), strlen(B));
}这篇关于NOJ 1224 编辑距离问题 (线性dp 分类)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
