POJ 3356 AGTC(经典DP Edit Distance)

题意:给出2个字符串x, y,长度为n,m,允许使用3种操作,求把x变成y需要的最小步骤,也就是要求两个字符串的编辑距离.

插入:在x的任意位置插入一个字符.

删除:在x的任意位置删除一个字符.

替换:在x的任意位置替换一个字符成任意字符.

设dp[i][j]为x后缀[i:]变成y的后缀[j:]所需要的最小步骤([i:]代表从i位置开始一直到尾部的字符串)

则:

如果x[i] == y[j],那么dp[i][j] = dp[i + 1][j + 1],不需要做任何操作.

如果x[i] != y[j],那么dp[i][j] = min(dp[i + 1][j + 1] + 1, dp[i][j + 1] + 1, dp[i + 1][j + 1] + 1).

解释下:

dp[i + 1][j + 1] + 1代表的是把x[i]替换成y[j],剩下的就是后缀[i + 1:]和后缀[j + 1:]的值了.

dp[i][j + 1] + 1代表的是在将y[j]插入到x[i]之前的位置,那么也就是剩下的后缀[i:]和后缀[j + 1:]的值了,因为y[j]和插入到x[i]之前的的字符抵消了.

dp[i + 1][j] + 1代表的删除x[i]位置的字符串,那么剩下也就是后缀[i + 1:]和后缀[j:]的值了,因为删除了x[i],在i后面的操作中总会出现和y[j]抵消掉的操作.

base cases: 

dp[i][m] = n- i因为要把[i:]变成[M:]需要n-i次删除操作才能变空.

dp[n][j] = m-j同理.

#include <algorithm>
#include <memory.h>
#include <cstdio>
using namespace std;
const int MAX = 1001;
#define min3(a, b, c) min((a), min((b), (c)))

short dp[MAX][MAX];
char A[MAX], B[MAX];
int main(int argc, char const *argv[]){
	int N, M;
	while(scanf("%d%s%d%s", &N, A, &M, B) == 4){
		memset(dp, 0, sizeof(dp));

		for(int i = 0; i < N; ++i){
			dp[i][M] = N - i;
		}
		for(int j = 0; j < M; ++j){
			dp[N][j] = M - j;
		}
		
		for(int i = N - 1; i >= 0; --i){
			for(int j = M - 1; j >= 0; --j){
				if(A[i] == B[j]){
					dp[i][j] = dp[i + 1][j + 1];
				}else{
					dp[i][j] = min3(dp[i + 1][j + 1] + 1, dp[i][j + 1] + 1, dp[i + 1][j] + 1);
				}
			}
		}
		printf("%d\n", dp[0][0]);
	}
	return 0;
}

POJ 3356 AGTC(经典DP Edit Distance),布布扣,bubuko.com

POJ 3356 AGTC(经典DP Edit Distance)

原文：http://blog.csdn.net/zxjcarrot/article/details/21289389