Problem Statement
设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
$A, B$ 均只包含小写字母。
第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A, B$ 的长度均小于 $2000$。
Output
只有一个正整数，为最少字符操作次数。
Sample Output
Constraints
对于 $100 %$ 的数据，$1 \le |A|, |B| \le 2000$。
Solving
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
61
62
63
64
65
66
67
68
69
70
71
|
const int N = 2005;
const int M = 0;
int dp[N][N];//表示s1取前i个字符变成s2取前j个字符所需要的最小操作次数
int dp2[N];
string s1,s2;
// a : s1 中插入一个字符的代价
// b : s1 中删除一个字符的代价
// c : s1 中替换一个字符的代价
void solve()
{
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int a = 1;
int b = 1;
int c = 1;
for(int i=1;i<=n;i++) dp[i][0] = i*b;
for(int j=1;j<=m;j++) dp[0][j] = j*a;
//dp[0][0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s1[i-1]==s2[j-1])
{
dp[i][j] = dp[i-1][j-1];
}
else
{
dp[i][j] = min({dp[i-1][j]+b,dp[i][j-1]+a,dp[i-1][j-1]+c});
}
}
}
cout << dp[n][m];
}
//由状态转移仅依赖上和左上和左:
//一维空间优化后的版本
void solvepromoted()
{
cin >> s1 >> s2;
int n = s1.size();
int m = s2.size();
int a = 1;
int b = 1;
int c = 1;
int leftup;//记录左上
int backup;//和leftup形成loop的中间变量
for(int j=1;j<=m;j++) dp2[j] = j*a;
//rep(1~n)rep(1~m)的情况下，空间压缩后dp[j-1]为左，更新前的dp[j]为上,leftup为左上;
for(int i=1;i<=n;i++)
{
//此时leftup代表每一行最开始的值:即dp[i-1][0] == (i-1)*b
leftup = (i-1)*b;
dp2[0] = i*b;
for(int j=1;j<=m;j++)
{
backup = dp2[j];//此时backup记录此时dp2[j]为后续dp2[j+1]作为左上元素
if(s1[i-1]==s2[j-1])
{
dp2[j] = leftup;
}
else
{
dp2[j] = min({dp2[j]+b,dp2[j-1]+a,leftup+c});
}
leftup = backup;
}
}
cout << dp2[m];
}
|