题解：SP6219 EDIST - Edit distance
_wzb_
·
·
题解
SP6219 EDIST - Edit distance
题目大意：
将 A 字符串转换为 B 字符串的最小次数
思路：
**状态转移方程**：
- 当 $A_i=B_i$ 时 $dp_{i,j}=dp_{i-1,j-1}$。
- 当 $A-i\ne B_i$时
1.修改字符，要修改这一位所以
$dp_{i,j}=dp_{i-1,j-1}+1$。
2.添加字符，要在这个位置加上一位所以 $dp_{i,j}=dp_{i-1,j}+1$。
3.删除字符，要删除这个位置上的数所以 $dp_{i,j}=dp_{i,j-1}+1$。
- 最终: $$\ dp_{i,j}= \min\begin{cases} dp_{i-1,j-1}\\dp_{i-1,j}\\dp_{i,j-1}&\end{cases}+1$$
## 代码：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string A,B; // 存储输入的两个字符串
ll dp[1000][1000]; // DP数组，dp[i][j]表示A前i个字符转B前j个字符的最小操作数
ll T;
signed main(){
cin>>T; // 读取测试用例数量
while(T--) // 处理每个测试用例
{
cin>>A>>B; // 读取两个字符串
ll Alen=A.size(); // 字符串A的长度
ll Blen=B.size(); // 字符串B的长度
// 初始化边界条件：
// 将A前i个字符转为空串需要i次删除操作
for(int i=1;i<=Alen;i++) dp[i][0]=i;
// 将空串转为B前j个字符需要j次插入操作
for(int i=1;i<=Blen;i++) dp[0][i]=i;
for(int i=1;i<=Alen;i++) // 遍历A的每个字符
{
for(int j=1;j<=Blen;j++) // 遍历B的每个字符
{
if(A[i-1]==B[j-1]) // 当前字符相同
{
// 无需操作，继承左上角的值
dp[i][j]=dp[i-1][j-1];
}
else // 当前字符不同
{
// 取三种操作的最小值加1：
// 1. dp[i-1][j]: 删除A[i-1]
// 2. dp[i][j-1]: 在A中插入B[j-1]
// 3. dp[i-1][j-1]: 替换A[i-1]为B[j-1]
dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
}
}
}
// 输出最终结果：将整个A转为整个B的最小操作数
cout<<dp[Alen][Blen];
}
return 0;
}
```