C++信息学奥赛

问题描述：给你两个单词word1和word2，请你计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

解题思路：

编辑距离（Levenshtein距离）是字符串处理中另一个经典的动态规划问题：

1. 设dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作数
2. 状态转移方程：
   • 如果word1[i-1] == word2[j-1]（当前字符相同）：dp[i][j] = dp[i-1][j-1]
   • 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     • dp[i-1][j] + 1：删除word1的第i个字符
     • dp[i][j-1] + 1：插入word2的第j个字符
     • dp[i-1][j-1] + 1：替换word1的第i个字符为word2的第j个字符
3. 初始条件：
   • dp[0][j] = j（将空字符串转换为word2的前j个字符需要j次插入）
   • dp[i][0] = i（将word1的前i个字符转换为空字符串需要i次删除）
4. 最终结果是dp[m][n]，其中m和n分别是word1和word2的长度

代码实现

// 编辑距离的动态规划解法
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 方法1：基础二维DP（O(mn)时间，O(mn)空间）
int minDistance1(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    
    // dp[i][j]表示word1前i个字符转换成word2前j个字符的最少操作数
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;  // 删除i个字符
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;  // 插入j个字符
    }
    
    // 填充dp数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                // 当前字符相同，不需要操作
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 取三种操作的最小值加1
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            }
        }
    }
    
    return dp[m][n];
}

// 方法2：空间优化（O(mn)时间，O(n)空间）
int minDistance2(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    
    // 只使用一维数组
    vector<int> dp(n + 1, 0);
    
    // 初始化第一行
    for (int j = 0; j <= n; j++) {
        dp[j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];  // 保存dp[i-1][j-1]
        dp[0] = i;        // 第i行第0列的值
        
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];  // 保存更新前的dp[j]，即dp[i-1][j]
            
            if (word1[i - 1] == word2[j - 1]) {
                dp[j] = prev;
            } else {
                dp[j] = min({dp[j], dp[j - 1], prev}) + 1;
            }
            
            prev = temp;  // 更新prev为下一轮的dp[i-1][j-1]
        }
    }
    
    return dp[n];
}

int main() {
    string word1 = "horse";
    string word2 = "ros";
    
    cout << "最少编辑操作数（方法1）: " << minDistance1(word1, word2) << endl;  // 3
    cout << "最少编辑操作数（方法2）: " << minDistance2(word1, word2) << endl;  // 3
    
    return 0;
}