洛谷 P2758 编辑距离题解

y0k1n0

2025 年 03 月 02 日

32 次浏览

暂无评论

1599字数

动态规划

# 洛谷 P2758 编辑距离 题解

## 题目描述

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

$A, B$ 均只包含小写字母。

## 输入

第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A, B$ 的长度均小于 $2000$。

## 输出

只有一个正整数，为最少字符操作次数。

## 解题思路

本题可以通过动态规划的方式解决， 状态的定义参考**最长公共子序列**

- 状态表示：
  - 集合：`dp[i][j]`表示`A`的前`i`个字符组成的字符串转换为`B`的前`j`个字符组成的字符串所需要的操作的集合
  - 属性：集合中所有操作的最小值
- 状态计算：
  - `dp[i][j]= min(dp[i][j], dp[i - 1][j] + 1)`: `A`的前`i`个字符组成的字符串转换为`B`的前`j`个字符组成的字符串所需要的最小操作步数， 可以是由`A`的前`i - 1`个字符组成的字符串转换为`B`的前`j`个字符组成的字符串对应的最小操作步数加上将`A`的第`i`个字母删除得到
  - `dp[i][j]= min(dp[i][j], dp[i][j - 1] + 1)`: `A`的前`i`个字符组成的字符串转换为`B`的前`j`个字符组成的字符串所需要的最小操作步数， 可以是由`A`的前`i`个字符组成的字符串转换为`B`的前`j - 1`个字符组成的字符串对应的最小操作步数加上在`A`的末尾添加`B[j]`得到
  - `if(A[i] != B[j]) dp[i][j]= min(dp[i][j], dp[i - 1][j - 1] + 1)`: `A`的前`i`个字符组成的字符串转换为`B`的前`j`个字符组成的字符串所需要的最小操作步数， 可以是由`A`的前`i - 1`个字符组成的字符串转换为`B`的前`j - 1`个字符组成的字符串对应的最小操作步数加上将`A`的第`i`个字母替换为`B`的第`j`个字母得到的
  - `if(A[i] == B[j]) dp[i][j]= min(dp[i][j], dp[i - 1][j - 1])`: `A`的前`i`个字符组成的字符串转换为`B`的前`j`个字符组成的字符串所需要的最小操作步数， 可以是由`A`的前`i - 1`个字符组成的字符串转换为`B`的前`j - 1`个字符组成的字符串对应的最小操作步数

## AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 2e3 + 10;
typedef pair<int, int> PII;
int dp[N][N];
PII cnt[N][N];
string s1, s2;
int n, m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> s1 >> s2;
    n = s1.length(), m = s2.length();
    s1 = ' ' + s1, s2 = ' ' + s2;
	memset(dp, 0x3f, sizeof dp);

dp[0][0] = 0;
	for(int i = 1; i <= n; i ++) dp[i][0] = i;
	for(int i = 1; i <= m; i ++) dp[0][i] = i;

for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
			if(s1[i] == s2[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
 		}
	}

cout << dp[n][m] << endl;

return 0;
}
```

最后修改：2025 年 03 月 07 日