一、题目

二、题解

1、解题思路：

1）通过观察我们发现，题目是典型的满足线性DP性质的题目，即满足

• 最优子结构（子问题取最优，最终的大问题必然最优）
• 无后效性（即当前下标i的取值与其后续下标(i~n)无关）
• 子问题重叠性（解决了子问题的重叠产生的时间浪费，即空间换时间）、

2）动态规划解题步骤：

1^#重述问题：

• 用最少的字符操作次数，将字符串$A$转化为$B$

2^#找到最后一步：

• 遍历到了A[i],B[j]，选择了某种操作，使得字符串A转化为字符串B

3^#去掉最后一步，问题变成了什么？

• 从字串A(1->i-1)，B[1->i-1]用最少的操作次数，将A转化为B

3）状态转移方程推导：

原问题答案=dp[i-1][j-1]+(对A[i],B[j]的处理操作):
if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
else if(a[i]!=b[j]) //此时不相等，那么我们就要分别处理三种情况
{
	dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
}

2、关键代码解析

• 即把状态转移方程复写

	string s1; cin >> s1; s1=' '+s1;
    string s2; cin >> s2; s2=' '+s2;    //使得下标从1开始计算
    int len1 = s1.size() - 1, len2 = s2.size() - 1;

    //初始化,当dp[i][0]时，说明另一个字符串为空，只需要把该字符串全部置空即可
    for (int i = 1; i <= len1; i++) dp[i][0] = i;
    for (int j = 1; j <= len2; j++) dp[0][j] = j;

    for (int i = 1; i <= len1; i++) //遍历字符串
    {
        for (int j = 1; j <= len2; j++)
        {
            if (s1[i] == s2[j])  //此时遍历到的两个数相等
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else  //不相等，同时枚举三种情况，找最小值 
            {
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
    cout << dp[len1][len2] << '\n';

这段代码的功能是 计算将字符串 s1 变成 s2 所需的最少编辑次数，即 编辑距离（Levenshtein Distance）。编辑操作包括：

1. 插入（Insert）：在 s1 中插入一个字符，使其匹配 s2。
2. 删除（Delete）：从 s1 中删除一个字符，使其匹配 s2。
3. 替换（Replace）：将 s1 的一个字符修改为 s2 的对应字符。

---

（1）输入字符串并处理索引

string s1; cin >> s1; s1=' '+s1;
string s2; cin >> s2; s2=' '+s2; 

• 读取两个字符串 s1 和 s2。
• 在 s1 和 s2 前面添加一个空格，这样索引从 1 开始，避免处理 0 索引的特殊情况，方便 dp 计算。

---

（2）计算字符串长度

int len1 = s1.size() - 1, len2 = s2.size() - 1;

• len1 是 s1 去掉额外空格后的长度。
• len2 是 s2 去掉额外空格后的长度。

---

（3）初始化 dp 数组

for (int i = 1; i <= len1; i++) dp[i][0] = i;
for (int j = 1; j <= len2; j++) dp[0][j] = j;

• dp[i][0] = i：如果 s2 是空串，只能 删除 s1 的所有字符，因此 dp[i][0] = i。
• dp[0][j] = j：如果 s1 是空串，只能 插入 s2 的所有字符，因此 dp[0][j] = j。

---

（4）动态规划计算 dp

for (int i = 1; i <= len1; i++) 
{
    for (int j = 1; j <= len2; j++)
    {
        if (s1[i] == s2[j])  
        {
            dp[i][j] = dp[i - 1][j - 1]; // 不需要额外操作
        }
        else  
        {
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
        }
    }
}

状态转移方程

• 如果 s1[i] == s2[j]，当前字符相同，不需要操作：

  dp[i][j] = dp[i-1][j-1];
  

• 如果 s1[i] ≠ s2[j]，可以选择：

  • 替换（Replace）：dp[i-1][j-1] + 1 （s1[i] 变为 s2[j]）
  • 插入（Insert）：dp[i][j-1] + 1 （在 s1 中插入 s2[j]）
  • 删除（Delete）：dp[i-1][j] + 1 （删除 s1[i]）

  取三者的最小值：

  dp[i][j] = min(min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j]) + 1;
  

---

3. 示例分析

示例 1

输入

horse
ros

计算过程

s1 → s2	操作	步数
horse → orse	删除 h	1
orse → rse	替换 o 为 r	2
rse → ros	替换 s 为 o	3

输出

3

---

示例 2

输入

intention
execution

计算过程

s1 → s2	操作	步数
intention → enention	替换 i 为 e	1
enention → exention	替换 n 为 x	2
exention → executnion	插入 c	3
executnion → execution	替换 n 为 i	4

输出

5

---

4. 复杂度分析

• 时间复杂度: O(n*m)，因为 dp 需要遍历 s1 和 s2 的所有字符。
• 空间复杂度: O(n*m)，因为 dp 数组占用 O(n*m) 的空间。

---

三、完整代码解析

//1、对于a,b两个字符串,我们使用最少的操作次数(op1,op2,op3),将字符串A转化为B
//2、对于a[i],b[j]做具体分析,选择了某个步骤o，使得a->b
//3、对于a(0~i-1),b(0~j-1),要求选择最少的次数,使得a->b
//原问题答案=对于a(0~i-1),b(0~j-1),要求选择最少的次数+1
#include <bits/stdc++.h>
using namespace std;

const int N = 2007;
int dp[N][N];

void solve()
{
    string s1; cin >> s1; s1=' '+s1;
    string s2; cin >> s2; s2=' '+s2;    //使得下标从1开始计算
    int len1 = s1.size() - 1, len2 = s2.size() - 1;

    //初始化,当dp[i][0]时，说明另一个字符串为空，只需要把该字符串全部置空即可
    for (int i = 1; i <= len1; i++) dp[i][0] = i;
    for (int j = 1; j <= len2; j++) dp[0][j] = j;
   // cout << s1[1] << ' ' << s2[1] << '\n';
    //if (s1[1] == s2[1]) cout << "YES" << '\n';
    for (int i = 1; i <= len1; i++) //遍历字符串
    {
        for (int j = 1; j <= len2; j++)
        {
            if (s1[i] == s2[j])  //此时遍历到的两个数相等
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else  //不相等，同时枚举三种情况，找最小值 
            {
                dp[i][j] = min(min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
     /*for (int i = 1; i <= len1; i++)
     {
         for (int j = 1; j <= len2; j++)
         {
             cout << dp[i][j] << ' ';
         }
         cout << '\n';
     }*/
    cout << dp[len1][len2] << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while (_--) solve();
    system("pause");
    return 0;
}