在算法学习的道路上，总有一些题目像拦路虎一样，让人望而生畏，却又不得不服。LeetCode第72题“编辑距离”就是这样一道经典的硬骨头。它不仅是动态规划章节里的“守门员”，geng是无数程序员面试时手撕代码的噩梦。你有没有想过当我们按下键盘上的退格键，或者在两个单词之间寻找某种微妙的相似度时背后到底隐藏着怎样的数学逻辑？今天我们就来彻底拆解这道题，不再死记硬背，而是真正理解如何用动态规划计算出那个神秘的数字。

一、 究竟什么是“编辑距离”？

在深入代码之前，我们得先搞清楚题目到底在问什么。所谓的“编辑距离”，学名叫Levenshtein Distance，听起来hen高大上，其实概念非常朴素。它指的是：将一个字符串转换成另一个字符串，所需要的Zui少操作次数。

这就好比你在玩拼图，手里拿着两块不同的图案，你需要通过Zui少的步骤把左边的变成右边的。在这个问题里我们手里的工具只有三种：

插入一个字符比如把 "ab" 变成 "abc"，我们在末尾塞进去一个 'c'。

删除一个字符比如把 "abcd" 变成 "abc"，我们把多余的 'd' 扔掉。

替换一个字符比如把 "abc" 变成 "adc"，我们把中间的 'b' 换成 'd'。

题目给了我们两个单词，`word1` 和 `word2`。我们的任务就是算出，把 `word1` 变成 `word2`，Zui少需要动多少次手。这不仅仅是算法题，在实际工程中，比如我在Zuo分布式BayesWipe系统进行数据清洗，或者你在用搜索引擎时的拼写纠错功Neng，底层的逻辑往往dou离不开这个距离的计算。

二、 为什么暴力法行不通？

刚kan到这道题时hen多人的第一反应是：“这不就是递归吗？我试着每一步dou去插入、删除、替换，然后kankan哪种步数Zui少。”

想法hen美好，现实hen骨感。Ru果你真的用递归去写，你会发现计算量呈指数级爆炸。因为子问题之间存在大量的重叠计算——比如在计算 "horse" 到 "ros" 的过程中，"hor" 到 "ro" 的距离可Neng会被重复计算成百上千次。这时候，动态规划这位“救世主”就该登场了。动态规划的核心思想就是空间换时间，把那些算过的子问题结果存起来下次需要时直接查表，不用再算一遍。

三、 动态规划五部曲：拆解核心逻辑

解决动态规划问题，有一套成熟的“心法”。我们不需要在那儿瞎猫碰死耗子，而是按部就班地定义状态、推导公式。

1. 定义DP数组：我们要存什么？

这是Zui关键的一步，也是Zui容易晕的地方。我们定义一个二维数组 `dp`，其中 `dp` 的含义必须非常明确：

dp 表示：将 word1 的前 i 个字符转换成 word2 的前 j 个字符，所使用的Zui少操作数。

这里有个细节要注意，为了处理“空串”的情况，我们的数组大小通常是 ` x `。其中 `n` 是 `word1` 的长度，`m` 是 `word2` 的长度。`dp` 就代表两个空串互相转换，那自然是 0 次操作。

2. 初始化边界：从零开始

在开始填表之前，先把边缘填好。这就像盖房子先打地基。

Ru果 `word1` 为空，我们要把它变成 `word2` 的前 `j` 个字符，怎么办？只Neng一个一个地插入字符。所以`dp = j`。同理，Ru果 `word2` 为空，我们要把 `word1` 的前 `i` 个字符全删了所以 `dp = i`。

这一步逻辑非常直观，但在代码实现时往往容易忽略下标的偏移，导致数组越界，这点我们后面细说。

3. 状态转移方程：核心中的核心

接下来就是Zui烧脑的部分了。我们要考虑 `word1` 的第 `i` 个字符和 `word2` 的第 `j` 个字符之间的关系。这里分两种情况：

情况一：两个字符相同

Ru果 `word1 == word2`，比如 `word1` 是 "abc"，`word2` 是 "adc"，当 `i=3, j=3` 时字符dou是 'c'。这时候我们不需要Zuo任何操作！当前的Zui小步数就等于它们前一步的Zui小步数。

公式就是：`dp = dp`。

情况二：两个字符不同

Ru果字符不一样，那我们就必须动用那三种操作了。我们要分别计算这三种操作的代价，然后取其中的Zui小值。

删除操作我们要把 `word1` 的第 `i` 个字符删掉。删掉之后问题就变成了：将 `word1` 的前 `i-1` 个字符转换成 `word2` 的前 `j` 个字符。所以代价是 `dp + 1`。

插入操作我们要在 `word1` 的第 `i` 个字符后面插入一个和 `word2` 一样的字符。插入之后`word1` 的前 `i` 个字符就匹配了 `word2` 的前 `j` 个字符，问题就变成了：将 `word1` 的前 `i` 个字符转换成 `word2` 的前 `j-1` 个字符。代价是 `dp + 1`。

替换操作我们把 `word1` 的第 `i` 个字符替换成 `word2` 的第 `j` 个字符。这样两个字符就匹配了剩下的任务就是处理前面的部分：将 `word1` 的前 `i-1` 个字符转换成 `word2` 的前 `j-1` 个字符。代价是 `dp + 1`。

所以当字符不相等时我们的状态转移方程就是这三个值的Zui小值：

`dp = min`

这个方程虽然kan着有点长，但只要理解了每个操作对下标的影响，其实并不难记。

四、 代码实战：TypeScript 实现与细节剖析

理论讲完了直接上代码。这里我用 TypeScript 写了一个版本，每一行dou加上了详细的注释，对应我们刚才拆解的逻辑。你Ke以试着在脑海中模拟一下矩阵填充的过程。

function minDistance: number {
  // 获取两个单词的长度
  let n = word1.length; 
  let m = word2.length;
  // 边界情况处理：Ru果有一个字符串是空串
  // 那么操作数就是另一个字符串的长度
  // 这里用 n * m == 0 来判断，比写两个 if geng简洁
  if  {
    return n + m;
  }
  // 初始化 dp 数组
  // 长度是 n+1 和 m+1，因为要包含“0个字符”的情况
  // 比如 dp 代表两个空串，无需操作
  const dp: number = Array.from => new Array.fill);
  // 边界状态初始化：word2 为空时
  // dp = i，意味着要把 word1 的前 i 个字符全删掉
  for  {
    dp = i;
  }
  // 边界状态初始化：word1 为空时
  // dp = j，意味着要不断插入 j 个字符来匹配 word2
  for  {
    dp = j;
  }
  // 开始填充 dp 数组
  // 双重循环遍历所有可Neng的 i 和 j 组合
  for  {
    for  {
      // 左：对应删除操作
      // dp 是删掉 word1 当前字符后的状态
      let left = dp + 1;
      // 下：对应插入操作
      // dp 是插入字符匹配 word2 当前字符后的状态
      let down = dp + 1;
      // 左下：对应替换或不操作
      // 先取 dp 作为基准
      let left_down = dp;
      // Ru果当前两个字符不相等，替换操作需要 +1
      // Ru果相等，left_down 就保持原样
      if  != word2.charAt) {
        left_down += 1;
      }
      // 核心逻辑：取三种操作的Zui小值作为当前状态的Zui优解
      dp = Math.min);
    }
  }
  // dp 存的就是Zui终结果：word1 完整转 word2 的Zui少操作数
  return dp;
}

五、 常见陷阱与调试心得

虽然代码不长，但真正写对并跑通，中间还是有不少坑的。我在刷这道题的时候，也踩过不少雷，这里分享几个易错点。

1. 下标的错位

这是Zui容易让人抓狂的地方。`dp` 数组的下标是从 0 到 `n`，而字符串的下标是从 0 到 `n-1`。所以当我们比较 `word1` 和 `word2` 的当前字符时必须用 `word1.charAt` 和 `word2.charAt`。Ru果你直接写成 `word1`，程序就会报错，或者读到错误的字符。这种“差一错误”在算法题中非常常见，一定要时刻警惕。

2. 边界条件的判断

代码中我特意加了一个 `if ` 的判断。这不仅仅是为了省事，geng是为了防止后续初始化数组时出现不必要的麻烦。比如 `word1` 为空，`word2` 长度为 5，直接返回 5 即可，没必要去初始化一个 `1x6` 的矩阵再填表。这种小优化在面试时Neng体现你的思维缜密程度。

3. 状态转移的直观理解

有时候死记公式容易忘，不如画个图。想象你在矩阵的左上角 ``，要走到右下角 ``。每次移动，你dou要付出代价。向右走代表插入，向下走代表删除，向右下对角线走代表替换或匹配。我们的目标就是找一条代价Zui小的路径。这样一想，`dp`、`dp`、`dp`这三个来源就非常清晰了。

六、 与思考

LeetCode 72题编辑距离，绝对是动态规划算法里的一颗明珠。它kan似复杂，三种操作让人眼花缭乱，但只要理清了状态定义和转移逻辑，一切dou会变得豁然开朗。

这道题不仅仅教会我们如何写代码，geng教会了我们一种解决问题的思维方式：面对复杂的大问题，不要试图一口气解决，而是把它拆解成一个个重叠的小问题，记录下中间结果，逐步推导出Zui终答案。这种思想在计算机科学中无处不在从图论中的Zui短路径到自然语言处理中的序列标注，douNengkan到动态规划的身影。

下次当你再遇到类似的“Zui值”、“Zui少步数”问题，或者在Zuo数据清洗需要计算字符串相似度时不妨回想一下这个 `dp` 矩阵。希望这篇文章Neng帮你彻底攻克这道难关，让动态规划成为你手中的一把利剑。刷题之路虽然枯燥，但每解开一道难题，那种成就感也是无可替代的。加油，Algorithm Boy！

---