线性动态规划-编辑距离

编辑距离的具体问题是这样的：给定两个字符串，你可以对一个字符串执行三种操作中的任何一种：
1、插入一个字符；
2、删除一个字符；
3、或替换一个字符。
编辑距离是将一个字符串转换成另一个字符串所需要的最少操作次数。

例如：
输入：
sfdqbw
gfdgw
输出：4

在动态规划的解法中，通常会构建一个二维的DP表，其中 dp[i][j] 表示将第一个字符串的前 i 个字符转换成第二个字符串的前 j 个字符所需的最少操作次数。通过填充这个表格，可以得到将整个第一个字符串转换成第二个字符串所需的最少操作次数。这个问题的解法体现了动态规划的核心思想：通过将大问题分解为小问题，并存储中间结果（这里是操作次数），来避免重复计算。

代码实现：

/**************************************************************** 
 * Description: 动态规划之编辑距离
 * Author: Alex Li
 * Date: 2023-11-21 11:21:57
 * LastEditTime: 2023-11-21 11:22:02
****************************************************************/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int editDistance(const string &str1, const string &str2) {
    int len1 = str1.length();
    int len2 = str2.length();

    // 创建一个二维动态数组
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));

    // 初始化边界条件
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }

    // 计算所有DP值
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                // 字符相同，无需操作
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 插入、删除、替换操作中选择一个最小值
                dp[i][j] = 1 + min({dp[i - 1][j],    // 删除
                                    dp[i][j - 1],    // 插入
                                    dp[i - 1][j - 1] // 替换
                                   });
            }
        }
    }

    return dp[len1][len2];
}

int main() {
    string str1, str2;
    cout << "Enter first string: ";
    cin >> str1;
    cout << "Enter second string: ";
    cin >> str2;

    cout << "Edit Distance: " << editDistance(str1, str2) << endl;

    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

线性动态规划-编辑距离