#cspjc2023w2. 2023csp-j初赛完善程序2
2023csp-j初赛完善程序2
2023csp-j初赛完善程序2
每小题3 分
1.第二题
(编辑距离) 给定两个字符串,每次操作可以选择删除(Delete)、插入(Insert)、替换(Replace),一个字符,求将第一个字符串转换为第二个字符串所需要的最少操作次数。
#include <iostream>
#include <string>
#include <vector>
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;
}
1.①处应填( ){{ select(1) }}
- j
- i
- m
- n
2.②处应填( ){{ select(2) }}
- j
- i
- m
- n
3.③处应填( ) {{ select(3) }}
- str1[i-1]==str2[j-1]
- str1[i]==str2[j]
- str1[i-1]!=str2[j-1]
- str1[i]!=str2[j]
4.④处应填( ) {{ select(4) }}
- dp[i-1][j-1]+1
- dp[i-1][j-1]
- dp[i-1][j]
- dp[i][j-1]
5.⑤处应填( ) {{ select(5) }}
- dp[i][j] + 1
- dp[i-1][j-1]+1
- dp[i-1][j-1]
- dp[i][j]