poj 3356 AGTC 编辑距离 经典DP

缘起

编辑距离是经典DP了, 我的博客中怎么能没有呢? poj 3356 AGTC

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定两个字符串x,y，要你求出x经过插入，删除，替换变成y所要的最少操作(x变动,y不需要变动)，即编辑距离。

【输入】
只需要处理一组数据, 输入见样例字符串长度不超过1000

【输出】
编辑距离

【样例输入】
10 AGTCTGACGC
11 AGTAAGTAGGC

【样例输出】
4

【限制】
1s

经典DP了. 令

1
2
3
4
5
6
7
8
设dp[i][j]表示字符串x[1...i]和字符串y[1...j]的最短编辑距离
当x[i] == y[j]时
dp[i][j] = min(dp[i-1][j-1](不需要编辑最后一位), dp[i-1][j] + 1(这个1是删除x[i]), dp[i][j - 1] + 1(这个1是插入一个x[i]=y[j]))
当x[i] != y[j]时,
dp[i][j] = min(dp[i-1][j-1] + 1(这个1是最后将x[i]替换成y[j]), dp[i-1][j] + 1(这个1是删除x[i]), dp[i][j-1] + 1(这个1是插入y[j]);
注意初始化
dp[i][0] = dp[0][i] = i;
最后的答案就是 dp[n][m]

这个dp过程是不是很眼熟? 和【1】中介绍的LCS问题非常相似哦~

则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

char x[1005], y[1005];
int n,m,dp[1005][1005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while (~scanf("%d%s%d%s", &n,x+1,&m,y+1))
	{
		for (int i =0; i<=m; i++)
		{
			dp[0][i] = i;
		}
		for (int i = 0; i<=n; i++)
		{
			dp[i][0] = i;
		} // dp初始化
		for (int i = 1;i<=n; i++)
		{
			for (int j = 1; j<=m; j++)
			{
				if (x[i]==y[j])
				{
					dp[i][j] = dp[i-1][j-1];
				}
				else
				{
					dp[i][j] = dp[i-1][j-1]+1;
				}
				dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
				dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
			}
		}
		printf("%d\n", dp[n][m]);
	}
	return 0;
}

ac情况

Status Accepted
Memory 4260kB
Length 741
Lang G++
Submitted 2019-10-05 19:16:04
Shared
RemoteRunId 20930518

参考

【1】https://yfsyfs.github.io/2019/07/28/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97%EF%BC%88LCS%EF%BC%89%E9%97%AE%E9%A2%98-hdu-1243-%E5%8F%8D%E6%81%90%E8%AE%AD%E7%BB%83%E8%90%A5/