1276:【例9.20】编辑距离

2023-12-14 12:30:30

算法分析

?动态规划:线性动规

1. 状态定义

集合:从字符串A转变为字符串B的方案
状态定义dp[i][j]表示A的前i个字符转变为B的前j个字符的操作次数最少的方案的操作次数。
初始状态
dp[0][j]为把空字符串转为长为j的字符串的操作次数,操作方法为:j次添加字符。所以dp[0][j] = j
dp[i][0]为把长为i的字符串转为空字符串的操作次数,操作方法为:i次删除字符。所以dp[i][0] = i

2. 状态转移方程

Ai表示A的前i个字符构成的子串。Bj表示B的前j个字符构成的子串。a[i]为A序列的第i个元素,b[j]为B序列的第j个元素。
分割集合:从A i?转变为B j的方案

如果a[i]等于b[j],那么只需要将A i?1 转变为B j?1 ,即可完成将A i 转变为B j ,操作次数为dp[i][j] = dp[i-1][j-1]

如果a[i]不等于b[j],可以有三种方案:添加、删除、修改

(1)在A i末尾添加字符b[j],那么添加后的字符串的末尾字符与B j的末尾字符相同,只需要先将A i转为B j?1,即可完成转变,操作次数为dp[i][j] = dp[i][j-1]+1

(2)删除A i末尾的字符a[i],那么就需要先将A i?1转变为B j,操作次数为:dp[i][j] = dp[i-1][j]+1

(3)将A i末尾的字符a[i]修改变为b[i],此时A i与B j末尾相同,那么只需要先将A i?1转为B j?1,即可完成转变。操作次数为:dp[i][j] = dp[i-1][j-1]+1

以上三种情况取最小值

【题解代码】

#include <bits/stdc++.h>
using namespace std;
#define N 2005
int dp[N][N];
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int l1 = s1.length(), l2 = s2.length();
    for(int i = 1; i <= l1; ++i)
        dp[i][0] = i;
    for(int j = 1; j <= l2; ++j)
        dp[0][j] = j;
    for(int i = 1; i <= l1; ++i)
        for(int j = 1; j <= l2; ++j)
        {
            if(s1[i-1] == s2[j-1])//第i与第j字符,在字符串中下标从0开始
                dp[i][j] = dp[i-1][j-1];
            else//添加 删除 修改 
                dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1), dp[i-1][j-1]+1);
        }
    cout << dp[l1][l2];
    return 0;
}

文章来源:https://blog.csdn.net/pheatonhb/article/details/134991167
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。