马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
我们定义 dp[j] 为将字符串 A[0..i-1] 转换为 B[0..j-1] 的最小操作数
状态转移
通过动态规划的思想，我们可以利用 状态转移方程 来计算 dp[j]。具体来说，dp[j] 的值可以由以下几种操作得到：
- 如果 A[i-1] == B[j-1]：
- 如果 A[i-1] 和 B[j-1] 相同，说明不需要对这两个字符做任何操作，那么我们只需从 dp[i-1][j-1] 继承结果：
dp[j] = dp[i-1][j-1]
- 如果 A[i-1] != B[j-1]：
- 删除操作：从 A[0..i-1] 删除一个字符，使其变为 A[0..i-2]，即 dp[j] = dp[i-1][j] + 1。
- 插入操作：从 B[0..j-1] 插入一个字符，变为 B[0..j-2]，即 dp[j] = dp[j-1] + 1。
- 替换操作：将 A[i-1] 替换为 B[j-1]，即 dp[j] = dp[i-1][j-1] + 1。
- 选择最小操作数：
- 由于我们需要最少的操作数，因此 dp[j] 是以上三种操作中最小的操作数。
边界条件
在动态规划的过程中，我们需要先初始化边界条件：
- dp[0]：将 A[0..i-1] 转换为空字符串，需要 i 次删除操作：
dp[0] = i
- dp[0][j]：将空字符串转换为 B[0..j-1]，需要 j 次插入操作：
dp[0][j] = j
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const int N = 1e4+4;
- int dp[N][N];
- int main() {
- string a, b;
- cin >> a >> b;
- int m = a.size();
- int n = b.size();
- for (int i = 0; i <= m; i++) {
- dp[i][0] = i;
- }
- for (int j = 0; j <= n; j++) {
- dp[0][j] = j;
- }
- for (int i = 1; i <= m; i++) {
- for (int j = 1; j <= n; j++) {
- if (a[i - 1] == b[j - 1]) {
- dp[i][j] = dp[i - 1][j - 1];
- }
- else {
- dp[i][j] = min({
- dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1]
- }) + 1;
- }
- }
- }
- cout << dp[m][n] << endl;
- return 0;
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
