先梳理一下之前的思路：
base case 是 i 走完 s1 或 j 走完 s2，可以直接返回另一个字符串剩下的长度。
对于每对儿字符 s1[i] 和 s2[j]，可以有四种操作：
if s1[i] == s2[j]:
啥都别做（skip）
i, j 同时向前移动
else:
三选一：
插入（insert）
删除（delete）
替换（replace）有这个框架，问题就已经解决了。读者也许会问，这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。这里需要递归技巧，先看下暴力解法代码：
int minDistance(String s1, String s2) {
int m = s1.length(), n = s2.length();
// i，j 初始化指向最后一个索引
return dp(s1, m - 1, s2, n - 1);
}
// 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
int dp(String s1, int i, String s2, int j) {
// base case
if (i == -1) return j + 1;
if (j == -1) return i + 1;
if (s1.charAt(i) == s2.charAt(j)) {
return dp(s1, i - 1, s2, j - 1); // 啥都不做
}
return min(
dp(s1, i, s2, j - 1) + 1, // 插入
dp(s1, i - 1, s2, j) + 1, // 删除
dp(s1, i - 1, s2, j - 1) + 1 // 替换
);
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}下面来详细解释一下这段递归代码，base case 应该不用解释了，主要解释一下递归部分。
都说递归代码的可解释性很好，这是有道理的，只要理解函数的定义，就能很清楚地理解算法的逻辑。我们这里 dp 函数的定义是这样的：
// 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
int dp(String s1, int i, String s2, int j) {记住这个定义之后，先来看这段代码：
if s1[i] == s2[j]:
return dp(s1, i - 1, s2, j - 1); # 啥都不做
# 解释：
# 本来就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)如果 s1[i] != s2[j]，就要对三个操作递归了，稍微需要点思考：
dp(s1, i, s2, j - 1) + 1, # 插入
# 解释：
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
# 别忘了操作数加一
dp(s1, i - 1, s2, j) + 1, # 删除
# 解释：
# 我直接把 s[i] 这个字符删掉
# 前移 i，继续跟 j 对比
# 操作数加一
dp(s1, i - 1, s2, j - 1) + 1 # 替换
# 解释：
# 我直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
# 同时前移 i，j 继续对比
# 操作数加一
现在，你应该完全理解这段短小精悍的代码了。还有点小问题就是，这个解法是暴力解法，存在重叠子问题，需要用动态规划技巧来优化。
怎么能一眼看出存在重叠子问题呢？后文 动态规划之正则表达式 有提过，这里再简单提一下，需要抽象出本文算法的递归框架：
int dp(i, j) {
dp(i - 1, j - 1); // #1
dp(i, j - 1); // #2
dp(i - 1, j); // #3
}
对于子问题 dp(i-1, j-1)，如何通过原问题 dp(i, j) 得到呢？有不止一条路径，比如 dp(i, j) -> #1 和 dp(i, j) -> #2 -> #3。一旦发现一条重复路径，就说明存在巨量重复路径，也就是重叠子问题。