dp[i - 1][j - 1]表示word1[0...i-2]转换word2[0...i-2]的最小转换步骤

dp[i ][j ]表示word1[0...i-1]转换word2[0...i-1]的最小转换步骤

则word1[0...i-1]=word1[0...i-2]+ai-1转换为word2[0...i-1]=word2[0...i-2] +bi-1可分解为如下步骤：

(1)    word1[0...i-1]=word1[0...i-2]+ai-1 转换为word1[0...i-1]=word2[0...i-2]+ai-1，即word1[0...i-2]转换为word2[0...i-2]

(2)    再将word2[0...i-2]+ai-1转换为word2[0...i-2] +bi-1，即将ai-1替换为bi-1

 由上面的分解可知，使用替换的递推关系可表示为dp[i][j] = dp[i - 1][j - 1] + 1

dp[i - 1][j] 表示word1[0...i-2]转换word2[0...i-1]的最小转换步骤，则word1[0...i-1]=word1[0...i-2]+ai-1转换为word2[0...i-1]可分解为两步：

(1)    word1[0...i-1]=word1[0...i-2]+ai-1删除ai-1,变为word1[0...i-2]

(2)    再将word1[0...i-2]转换为word2[0...i-1]

由上面的分解可知，使用删除的递推关系可表示为dp[i][j] = dp[i - 1][j] + 1

dp[i][j - 1] 表示word1[0...i-1]转换word2[0...i-2]的最小转换步骤，则word1[0...i-1]转换为word2[0...i-1] = word2[0...i-2] +bi-1可分解为

(1)    word1[0...i-1]转换为word2[0...i-2]

(2)    再将word2[0...i-2]转换为word2[0...i-1] = word2[0...i-2] +bi-1，即在word2[0...i-2]的基础上插入bi-1

由上面的分解可知，使用插入的递推关系可表示为dp[i][j] = dp[i][j - 1] + 1

class Solution {

public:

    int minDistance(string word1, string word2) {

        int row = word1.size();

        int col = word2.size();

        vector >dp(row+1, vector(col+1, 0));

        for (int i=1; i<=row; i++)

            dp[i][0] = i;//从长度为i的字符串到空串需要变换i次

        for (int j=1; j<=col; j++)

            dp[0][j] = j;//从长度为0的空字符串到长度为j的字符串需要变换j次

        for (int i=1; i<=row; i++){

            for (int j=1; j<=col; j++){

                if (word1[i-1] == word2[j-1])

                    dp[i][j] = dp[i-1][j-1];

                else

                    dp[i][j] = min(min(dp[i-1][j-1]+1,dp[i-1][j] +1), dp[i][j-1]+1 );

            }

        }

        return dp[row][col];

    }

};