CSP-J 2023 入门级 第一轮 完善程序（2）

【题目】

CSP-J 2023 入门级 第一轮 完善程序（2）
(2)(编辑距离)给定两个字符串，每次操作可以选择删除(Delete)、插入(insert)替换(Replace)个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。
试补全动态规划算法。

#include 
#include 
#include 
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j]=1+min(dp[i][j - 1],dp[i - 1][j], ⑤);
         }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Mininum number of operation:" 
          << edit_dist_dp(str1, str2) << endl;
    return 0;
}

38. ①处应该填(   )
	 A. j               B. i             C. m              D. n

39. ②处应该填(   )
	 A. j               B. i             C. m              D. n

40. ③处应该填(   )
	 A. str1[i – 1] == str2[j – 1]    B. str1[i] == str2[j]
	 C. str1[i – 1] != str2[j – 1]    D. str1[i] != str2[j]

41. ④处应该填(   )
	 A. dp[i – 1][j – 1] + 1      		B. dp[i – 1][j – 1]
	 C. dp[i – 1][j]               		D. dp[i][j – 1]

42. ⑤处应该填(   )
	 A. dp[i][j] + 1                   B. dp[i – 1][j – 1] + 1
	 C. dp[i – 1][j – 1]              	D. dp[i][j] 


## 【题目考点】
#### 1. 线性动态规划
- 求最长公共子序列

##  【解题思路】
```cpp
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
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

min函数求三个数的最小值

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Mininum number of operation:" 
          << edit_dist_dp(str1, str2) << endl;
    return 0;
}
1
2
3
4
5
6
7

主函数输入两个字符串，输出两个字符串的编辑距离。

int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j]=1+min(dp[i][j - 1],dp[i - 1][j], ⑤);
         }
    }
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

该题具体解题思路请看：信息学奥赛一本通 1276：【例9.20】编辑距离
请先点击进入上面的链接，理解解题思路，以下针对填空作简略介绍：
用两层vector设状态数组（作用相当于二维数组）dp。
dp[i][j]指表示str1的前i个字符转变为str2的前j个字符的最少操作次数。
i为0时，str1的前0个字符转变为str2的前j个字符的操作方案为j次插入，操作次数为j。(1)填j，选A。
j为0时，str1的前i个字符转变为str2的前0个字符的操作方案为i次删除，操作次数为i。(2)填i，选B。
如果str1第i字符str1[i-1]与str2第j字符str2[j-1]相同，(3)填A。
那么dp[i][j]就是str1的前i-1个字符转变为str2的前j-1个字符的最少操作次数，(4)填B。
否则，dp[i][j]就是最后一次进行插入、或删除、或修改时的最少操作次数。如果最后一次将str1[i-1]修改为str2[j-1]，那么接下来要将str1的前i-1个字符转变为str2的前j-1个字符，(5)填C。

【答案】

38. A
39. B
40. A
41. B
42. C