1. 解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。
2. base case 是i走完s1或j走完s2，可以直接返回另一个字符串剩下的长度。
3. 对于每对字符s1[i]和s2[j]，可以有四种操作：
   
   这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。这里需要递归技巧，理解需要点技巧，先看下代码：递归版本
   

def dp(i, j) -> int
返回 s1[0..i] 和 s2[0..j] 的最小编辑距离

if s1[i] == s2[j]:
    return dp(i - 1, 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(i, j - 1) + 1,    # 插入
# 解释：
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
# 别忘了操作数加一

dp(i - 1, j) + 1,    # 删除
# 解释：
# 我直接把 s[i] 这个字符删掉
# 前移 i，继续跟 j 对比
# 操作数加一

dp(i - 1, j - 1) + 1 # 替换
# 解释：
# 我直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
# 同时前移 i，j 继续对比
# 操作数加一

这个解法是暴力解法，存在重叠子问题，需要用动态规划技巧来优化，下面是动态规划版本：

• 首先明确 dp 数组的含义，dp 数组是一个二维数组，长这样：
  dp[i][j]的含义和之前的 dp 函数类似：

#递归版本
def dp(i, j) -> int   
# 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离

#动态规划版本
dp[i-1][j-1]  注意这里i-1和j-1，因为数组长宽多了一位
# 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离

dp 函数的 base case 是i,j等于 -1，而数组索引至少是 0，所以 dp 数组会偏移一位，dp[..][0]和dp[0][..]对应 base case

当然既然每个dp[i][j]只和它附近的三个状态有关，空间复杂度是可以压缩成 O(min(M,N)) 的（M，N 是两个字符串的长度）