Description
Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:
Certainly, we would like to minimize the number of all possible operations.
IllustrationA G T A A G T * A G G C | | | | | | | A G T * C * T G A C G C
Deletion: * in the bottom line
Insertion: * in the top line
Change: when the letters at the top and bottom are distinct
This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we would be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like
A G T A A G T A G G C | | | | | | | A G T C T G * A C G C
and 4 moves would be required (3 changes and 1 deletion).
In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≥ m.
Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.
Write a program that would minimize the number of possible operations to transform any string x into a string y.
Input
The input consists of the strings x and y prefixed by their respective lengths, which are within 1000.
Output
An integer representing the minimum number of possible operations to transform any string x into a string y.
Sample Input
10 AGTCTGACGC 11 AGTAAGTAGGC
Sample Output
4
设dp[i][j]为第一个串到i为止，第二个串到j为止 的最少次数。
dp[i][j] = dp[i-1][j-1] (s[i] == s[j])
dp[i][j] = Max{dp[i][j] , dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1}
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define lson o <<
1, l, m
#define rson o <<
1|1, m+1, r
using namespace std;
typedef long
long LL;
const int MAX=0x3f3f3f3f;
const int maxn
= 1000+10;
int n, m, dp[maxn][maxn];
char a[maxn], b[maxn];
int Min(int x,
int y,
int z, int w)
{
int ans = MAX;
if(x
< ans) ans = x;
if(y
< ans) ans = y;
if(z
< ans) ans = z;
if(w
< ans) ans = w;
return ans;
}
int main()
{
while(~scanf("%d",
&n))
{
scanf("%s", a+1);
scanf("%d%s",
&m, b+1);
memset(dp, MAX,
sizeof(dp));
for(int i
= 0; i
<= m; i++) dp[0][i]
= i;
for(int i
= 0; i
<= n; i++) dp[i][0]
= i;
for(int i
= 1; i
<= n; i++)
for(int j
= 1; j
<= m; j++)
{
if(a[i]
== b[j]) dp[i][j]
= dp[i-1][j-1];
dp[i][j]
= Min(dp[i][j], dp[i-1][j-1]+1,
dp[i-1][j]+1, dp[i][j-1]+1);
}
printf("%d\n", dp[n][m]);
}
return 0;
}
POJ 3356 AGTC （编辑距离 DP）,布布扣,bubuko.com
原文：http://blog.csdn.net/u013923947/article/details/38387003