解题思路：动态规划

• 定义状态
  设 $dp[i][j]$ 表示 将 word1[0:i] 转换为 word2[0:j] 需要的最少操作数。

• 状态转移方程

  1. 如果 word1[i-1] == word2[j-1]（最后一个字符相同，不需要操作）：$$dp[i][j] = dp[i-1][j-1]$$

Leetcode 95.编辑距离-原题链接

题目描述

给定两个单词 word1 和 word2，请返回将 word1 转换为 word2 所需的最少操作数。

允许的操作如下：

• 插入 一个字符
• 删除 一个字符
• 替换 一个字符

输入描述

输入包含两行：

• 第一行是字符串 word1（$0 \leq |word1| \leq 500$）。
• 第二行是字符串 word2（$0 \leq |word2| \leq 500$）。

word1 和 word2 仅由小写英文字母组成。

输出描述

输出一行，表示将 word1 转换为 word2 所需的最少操作数。

样例输入 1

horse
ros

样例输出 1

3

说明：

1. horse → rorse （替换 h → r）
2. rorse → rose （删除 r）
3. rose → ros （删除 e）

样例输入 2

intention
execution

样例输出 2

5

说明：

1. intention → inention （删除 t）
2. inention → enention （替换 i → e）
3. enention → exention （替换 n → x）
4. exention → exection （替换 n → c）
5. exection → execution （插入 u）