翻车笔记_ luogu2758 编辑距离 [序列DP]

你体会过看了[普及-]题解还不会的恐惧嘛…
看来我还真是不会DP啊…

懵逼的 题目

传送至 Luogu

扯淡的 题解

f[i][j]拿A前i个字符转到B前j个字符的代价(记好了这个定义…要不然后面直接看不懂)
转移:

  • 相等: 直接等于f[i - 1][j - 1]没什么好说的
  • 不相等:
    • 改变: 把A[i]改成B[j], 等于f[i - 1][j - 1]也没什么好说的
    • 删除: 删掉了A[i] A[1 ~ i]变成了A[1 ~ (i - 1)], 所以是f[i - 1][j]
    • 插入: 插入了B[j]A[i]之前, 变成了f[i + 1][j], 且A[i] == B[j], 所以f[i + 1][j] == f[i + 1 - 1][j - 1]f[i][j - 1]

沙茶的 代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define MAXN (2000 + 5)
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int m;
string a, b;
int ans = 0;
int f[MAXN][MAXN];
int tmin(int, int, int);
void dp();
int main()
{
cin >> a >> b;
n = a.length();
m = b.length();
dp();
printf("%d", ans);
return 0;
}
void dp()
{
memset(f, 0, sizeof(f));
char xa[MAXN];
char xb[MAXN];
for (int i = 1; i <= n; i++)
xa[i] = a[i - 1];
for (int i = 1; i <= m; i++)
xb[i] = b[i - 1];
for (int i = 1; i <= n; i++)
f[i][0] = i;
for (int i = 1; i <= m; i++)
f[0][i] = i;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (xa[i] == xb[j])
{
f[i][j] = f[i - 1][j - 1];
}
else
{
f[i][j] = tmin(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
}
//printf("%d %d: %d\n",i, j, f[i][j]);
}
}
ans = f[n][m];
}
int tmin(int xx, int xxx, int xxxx)
{
xx = min(xx, xxxx);
return min(xx, xxx);
}

By 被beat的 Cansult