/*****定义状态：DP[i][j]其中i表示word1前i个字符，j表示Word2前i个字符DP[i][j]表示单词1前i个字符匹配单词2前j个字符，最少变换次数；状态转移：for i:[0,m]    for j:[0,n]    if(word1[i-1]==word2[j-1])        DP[i][j]=DP[i-1][j-1];    else        DP[i][j]=min(DP[i-1][j],DP[i][j-1],DP[i-1][j-1])+1;return DP[m][n];******/class Solution {public:    int minDistance(string word1, string word2) {        int m=word1.size(),n=word2.size();        vector
     
      
        > DP(m+1,vector(n+1,0));        //初始化        for(int i=0;i<=m;i++){            DP[i][0]=i;        }        for(int j=0;j<=n;j++){            DP[0][j]=j;        }        //状态转移        for(int i=1;i<=m;i++){            for(int j=1;j<=n;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],DP[i][j-1]),DP[i-1][j-1])+1;            }        }        return DP[m][n];    }};