编辑距离问题用动态规划求解，定义dpi为word1前i字符变word2前j字符的最少操作数，初始化边界dp0=j、dpi=i，状态转移：相等则dpi=dpi−1，不等则dpi=1+min(dpi−1,dpi,dpi−1)，最终答案为dpm。
动态规划解决编辑距离问题，本质是把“两个字符串怎么变最少步”拆解成一张二维表，一格一格填出来。关键不在套公式，而在理解每个格子代表什么、为什么那样更新。
明确状态定义：dp[i][j] 是前缀之间的最小代价
定义 dp[i][j] 为：将 word1 的前 i 个字符 变成 word2 的前 j 个字符 所需的最少操作数。
注意：i 和 j 表示长度（不是下标），所以 dp 数组大小是 (m+1) × (n+1)，其中 m = word1.length()，n = word2.length()。
初始化边界：空串转换只能靠删或插
当一边为空时，操作方式唯一：
- 若 word1 为空（i = 0），要把空串变成 word2 的前 j 个字符，只能插入 j 次 → dp[0][j] = j
- 若 word2 为空（j = 0），要把 word1 的前 i 个字符变为空串，只能删除 i 次 → dp[i][0] = i
状态转移：字符相等直接继承，不等就试三种操作
对每个位置 (i, j)，比较 word1[i−1] 和 word2[j−1]（注意下标偏移）：
- 如果相等：无需操作，直接复用左上角结果 → dp[i][j] = dp[i−1][j−1]
- 如果不等：尝试三种操作，取最小值再加 1：
• 删除 word1[i−1] → dp[i−1][j] + 1
• 插入 word2[j−1] → dp[i][j−1] + 1
• 替换 word1[i−1] 为 word2[j−1] → dp[i−1][j−1] + 1
→ dp[i][j] = 1 + min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])
代码实现要点：索引别错、循环从1开始
Java 实现时需注意：
- 声明数组：int[][] dp = new int[m + 1][n + 1];
- 两层 for 循环都从 i = 1 到 m、j = 1 到 n
- 字符比较写法：word1.charAt(i - 1) == word2.charAt(j - 1)
- 最终答案就是 dp[m][n]，即整串转换的最小代价
