《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（35）山河社稷图展开 - 编辑距离（字符串DP）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（35）山河社稷图展开 - 编辑距离（字符串DP）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的山河社稷图，图中有一卷古老的山河社稷图，图面闪烁着神秘的光芒。图前有一块巨大的石碑，上面刻着一行文字：“欲展此图，需以山河社稷图之力，编辑距离，字符串DP显真身。”

哪吒定睛一看，石碑上还有一行小字：“字符串"intention"和"execution"的编辑距离为5。”哪吒心中一动，他知道这是一道关于计算两个字符串之间最小编辑距离的难题，需要通过动态规划的方法来解决。

暴力解法：山河社稷图的初次尝试

哪吒心想：“要计算两个字符串之间的编辑距离，我可以尝试所有可能的编辑操作。”他催动山河社稷图之力，通过递归的方式，枚举所有可能的插入、删除和替换操作，计算最小编辑距离。

int minDistance(string word1, string word2) {
   
    int m = word1.size();
    int n = word2.size();
    if (m == 0) return n;
    if (n == 0) return m;
    if (word1[0] == word2[0]) {
   
        return minDistance(word1.substr(1), word2.substr(1));
    }
    int insert = minDistance(word1, word2.substr(1));
    int deleteOp = minDistance(word1.substr(1), word2);
    int replace = minDistance(word1.substr(1), word2.substr(1));
    return 1 + min({
   insert, deleteOp, replace});
}

哪吒成功地计算了编辑距离，但山河社稷图的光芒却黯淡了下来。他意识到，这种方法虽然可行，但时间复杂度极高，尤其是当字符串很长时，灵力消耗巨大。

C++语法点

在C++中，动态规划是解决编辑距离问题的常用方法。以下是一些重要特性：

• 二维数组：

  • 使用vector<vector<int>>表示动态规划表。
  • 常用操作：
    • dp[i][j]：访问第i个字符、第j个字符时的最小编辑距离。
    • 初始化二维数组：vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0))。

• 动态规划：

  • 通过状态转移方程dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (word1[i-1] == word2[j-1] ? 0 : 1))计算当前状态的最小编辑距离。

高阶优化：字符串DP的智慧

哪吒元神中突然浮现金色铭文——「山河社稷图展开，字符串DP显真身」。他意识到，可以通过动态规划的方法，优化编辑距离的计算过程。

哪吒决定使用动态规划，创建一个二维数组dp，其中dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小编辑距离。通过状态转移方程，他成功地计算了最小编辑距离，而且灵力消耗大幅减少。

int minDistance(string word1, string word2) {
   
    int m = word1.size();
    int n = word2.size