定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。将字符串 AA 变成字符串 BB 的最少操作步数，称为字符串 AA 到字符串 BB 的编辑距离。字符串 “ABCDEFG” 到字符串 “BADECG” 的编辑距离为____。
题目答案 3
解析
我们也可以通过自己观察发现，我们需要把第一个字符串的 ‘A’ 删除，’C’ 改成 ‘A’，’F’ 改成 ‘C’ 即可变成第二个字符串，编辑距离为 3。

题目解析

这个程序用到了递归，我们可以借助表格来计算。

其实可以发现 solve(n,m) = solve(n, m - 1) + solve(n - 1, m - 1)solve(n,m)=solve(n,m−1)+solve(n−1,m−1)。