两个字符串s1和s2可以任意增删改字符串，增、删、改均算一步操作，问二者达到相同的字符串时最少的编辑次数。即问从s1变为s2，最少要几步。另外，s1增加一个字符与s2删除一个字符效果一样，s2增加一个字符与s1删除一个字符效果一样，s1改一个字符与s2改一个字符效果一样，将6项操作缩减为3项，考虑这3项操作的步数。设dp[i][j]表示s1[:i]和s2[:j]的最小编辑距离，dp.shape为[n1+1, n2+1]，dp[0][j]=j, dp[i][0]=i，for(i=1; i<=n1; i++){for(j=1; j<=n2; j++){if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1];else dp[i][j]=min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1;}}，当遍历的s1[i]和s2[j]相等时，dp[i+1][j+1]即dp[i][j]，毋须多编辑一步；不相等时，dp[i][j]基础上改s1的字符、dp[i-1][j]基础上s1插入字符、dp[i][j-1]基础上s2插入字符，取最小的操作数。dp[n1][n2]即为解。
参考链接：72. 编辑距离