从编辑距离问题学字符串的动态规划

---

解决两个字符串的动态规划问题，一般都是使用两个指针分别指向两个字符串的最后，然后一步一步地

向前走，不断地缩小问题的规模，进而找出最优解，下面先看题吧：

一、问题描述

Leetcode 72 编辑距离 ，题目简述如下

两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数步数，你可以对一个单

词进行如下三种操作：

• 插入一个字符

• 删除一个字符

• 替换一个字符

我想大部分人看到这个问题后，思考的方式和我是一样的，就是如何在word1中找到尽可能多的出现在

word2中的字符，并尽可能保留住；但实际上单是找到重复的字符还是不够的，我们还必须关注它们出现的

顺序，顺序不一样该删就删，毫不留情。实际上我们所关注的只是步数，删除、插入和替换都是一样的

其实这个问题已经露出了动态规划的马脚了，因为它给了我们三个选择，就是在比较两个字符串的字母

时如何选择策略，那当然是哪种策略的转化步数最小就是哪种了，这不就是在寻找最优子问题嘛

二、算法思想的描述

1.初始化两个指针分别指向两个字符串的末尾

2.比较两个指针所指字符，如果字符相同，说明这个位置对编辑距离的结果不会造成影响

如果不相同，那么就选择3种策略中，所需转化步数最小的那种

3.还会出现两种基本的情况：

• 指针已经遍历完word1时，word2还没有被遍历完，只能不断地向word1中插入元素了

• 指针已经遍历完word2时，word1还没有被遍历完，只能不断地删除word1中的元素了

三、代码实现

我们假设 i , j指针分别指向word1和word2中的最后一个字符，代码可以这样写的

public int minDistance(String word1,String word2){
    //分别初始化指向最后一个索引
    return dp(word1.length() - 1,word2.length() - 1);
}

public int dp(int i,int j){
    if(i == -1) return j + 1;   //word1遍历完，需要插入word2中剩余的所有元素，步数就是word2剩余的长度
    if(j == -1) return i + 1;   //word2遍历完，需要删除word1中剩余的所有元素，步数就是word1剩余的长度
    if(word1.charAt(i) == word2.charAt(j)) return dp[i-1][j-1]; //元素相同对编辑距离的结果不影响
    //否则取三种选择中转换步数最少的那个
    else: return Math.min(dp(i,j-1)+1,Math.min(dp(i-1,j)+1,dp(i-1,j-1)+1));
    //dp(i-1,j)表示将word1中的元素进行删除，直接把s[i]中这个元素删除了，直接前移i
    //dp(i,j-1)表示对word1进行插入操作,需要将word2中的指针前移
    //dp(i-1,j-1) 表示将word1对应位置的字符替换成word2中的字符，i,j都需要向前移动
}

对于上述解法显然是存在重叠子问题的，优化的方式就是备忘录和DP Table了

#备忘录的算法实现
def minDistance(s1,s2) -> int:
    memo = dict()     #可以使用字典来存储每一个dp(i,j)的转化步数
    def dp(i,j):
        if (i,j) in memo:
            return memo[(i,j)]
        if(s1[i] == s2[j]):
            memo[(i,j)] = 选择最优的转化步数
        else:
            memo[(i,j)] = 选择最优的转化步数
        return memo[(i,j)]
    return dp(len(s1) - 1,len(s2) - 1)

dp数组的解法：定义状态 dp[i] [j] 表示word1[0....i-1] 和 word2[0.....j-1]的最小编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(),n = word2.length();
        int[][] dp = new int[m+1][n+1];
        //数组的索引最小为0
        //如果word2为空串需要将word1中的每个元素都删除
        for(int i = 1;i <= m;i++){
            dp[i][0] = i;
        }
        //如果word1为空串需要将不断插入word2中的元素
        for(int j = 1;j <= n;j++){
            dp[0][j] = j;
        }

        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                }
            }
        }
        //返回word1[0.....m-1]和word2[0....n-1]的最小编辑距离
        return dp[m][n];
    }
}

如果想要知道如何操作只需在做最优选择时将当前结果记录下来即可