经典的利用动态规划法解决匹配问题的实例

题目:

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

    插入一个字符
    删除一个字符
    替换一个字符

代码如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        //先得到word1与word2的长度分别为n与m
        int n=word1.length();
        int m=word2.length();
        //如果二者中至少有一个大小为0则需要使用的最少操作数就是不为0的单词的大小(即删除这个单词的次数)
        if(m*n==0) return m+n;
        //设计DP数组有n+1个元素每个元素为大小为m+1的动态数组
        vector> DP(n+1,vector(m+1));
        //其中DP[i][j]的意义是word1的前i个单词到word2的前j个单词所使用的最少操作数
        //先进行i为0或者j为0的初始化
        for(int i=0;i<=n;i++){
            DP[i][0]=i;
        }
        for(int i=0;i<=m;i++){
            DP[0][i]=i;
        }
        //遍历DP数组中的每一个数值得到其应有的值
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int left=DP[i-1][j]+1;
                int right=DP[i][j-1]+1;
                int down=DP[i-1][j-1];
                if(word1[i-1]!=word2[j-1]) down=down+1;
                DP[i][j]=min(left,min(right,down));
            }
        }
        return DP[n][m];
    }
};

具体动态规划的思想解释如下:

首先得到word1与word2的大小分别为n与m,对于如果其中一个大小为0的情况,则所需要的最少步数就是另一个不为0的单词的大小(即将其全部删除就是最小步数),因此如果(m*n==0)输出m+n即可,时候设计二维数组DP(包含n+1个元素,每个元素均为大小为m+1的动态数组),其中DP[i][j]的作用为word1的前i个字符组成的单词到word2的前j的字符组成的单词所需要的最小步数,首先初始化DP[i][0]为i,DP[0][i]为i具体原因就是之前所说的一方为0的情况,之后遍历整个二维数组DP进行赋值,具体DP[i][j]的情况其实依靠于DP[i-1][j],DP[i][j-1],DP[i-1][j-1]其中DP[i-1][j]就是从word1的前i-1个单词到word2的前j个单词所需要的最小步数,因此DP[i][j]的值至少为DP[i-1][j],即在DP[i-1][j]的基础上进行一次在word1处添加一个字符的操作,此时是该种办法的最小值,同理DP[i][j]的值不得大于DP[i][j-1]+1,最后对于DP[i-1][j-1]要先判断word1[i-1]与word2[j-1]是否相等如果相等则DP[i][j]的最小值就等于DP[i-1][j-1]如果不相等就再次基础上加一即DP[i-1][j-1]+1(可以理解为将word1的第i个字符替换为word2的第j个字符),因此令left=DP[i-1][j]+1,right=DP[i][j-1]+1,down=DP[i-1][j-1](如果末尾元素不相等还需要加一),则DP[i][j]的值就是left,right,down中的最小值,最终输出DP[n][m]即为所求！