【LeetCode 72】编辑距离（C语言详解 + DP公式推导）

一、题目描述给你两个单词word1和word2请返回将word1转换成word2所使用的最少操作数。你可以进行三种操作插入一个字符删除一个字符替换一个字符示例输入word1 horse, word2 ros 输出3输入word1 intention, word2 execution 输出5二、解题思路经典二维 DP这题本质是字符串动态规划的经典模型编辑距离 / Levenshtein Distance。关键在于把问题拆成“前缀之间的最优解”三、状态定义核心我们定义dp[i][j] 表示 word1 前 i 个字符 转换为 word2 前 j 个字符 的最小操作数也就是word1[0...i-1] → word2[0...j-1]四、状态转移方程重点1️⃣ 如果当前字符相等word1[i-1] word2[j-1] dp[i][j] dp[i-1][j-1] 不需要操作2️⃣ 如果当前字符不相等我们有三种选择dp[i][j] min( dp[i-1][j] 1, // 删除 dp[i][j-1] 1, // 插入 dp[i-1][j-1] 1 // 替换 )三种操作解释操作含义删除删除 word1[i-1]插入插入 word2[j-1]替换把 word1[i-1] 改成 word2[j-1]五、初始化dp[0][j] j // 空串 - 插入 j 次 dp[i][0] i // 删除 i 次六、完整 C 代码实现#include stdio.h #include stdlib.h #include string.h int min(int a, int b) { return a b ? a : b; } int minDistance(char* word1, char* word2) { int m strlen(word1); int n strlen(word2); int** dp (int**)malloc((m 1) * sizeof(int*)); for (int i 0; i m; i) { dp[i] (int*)malloc((n 1) * sizeof(int)); } // 初始化 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 (word1[i - 1] word2[j - 1]) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] min( dp[i - 1][j] 1, min( dp[i][j - 1] 1, dp[i - 1][j - 1] 1 ) ); } } } int res dp[m][n]; // 释放内存 for (int i 0; i m; i) { free(dp[i]); } free(dp); return res; }七、示例推导理解 DP以word1 horse word2 ros核心变化horse - rorse (替换 h→r) rorse - rose (删除 r) rose - ros (删除 e) 总共 3 步八、复杂度分析时间复杂度O(m * n)空间复杂度O(m * n)九、进阶优化面试加分可以优化为一维 DP滚动数组空间复杂度降为O(n)但需要注意“左上角值”的保存十、总结面试必背dp[i][j] word1[i-1] word2[j-1] ? dp[i-1][j-1] : min( dp[i-1][j] 1, dp[i][j-1] 1, dp[i-1][j-1] 1 )