[数据结构与算法]LeetCode 72 编辑距离

思路：动态规划

稀里糊涂的写出来了？？？？？

出口：如果有一个串为空，则操作次数为另一个串的长度

状态转移方程:????

class Solution {
public:
    int minDistance(string word1, string word2) {
//dp[i][j]表示word1[0:i)要变成word[0:j)最少操作数
//i=0,dp[i][j]=j;word1添加j个数为word2
//j=0，dp[i][j]=i;word1删除i个数为word2
//如果word1[i-1]==word2[j-1],dp[i][j]=dp[i-1][j-1]
//否则dp[i][j]=dp[i-1][j-1]+1,把word1[i-1]换成word2[j-1]
vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1));
for(int i=0;i<=word1.size();i++)
{
    dp[i][0]=i;
}
for(int j=0;j<=word2.size();j++){
    dp[0][j]=j;
}
for(int i=1;i<=word1.size();i++)
{
    for(int j=1;j<=word2.size();j++)
    {
        if(word1[i-1]==word2[j-1])
        dp[i][j]=dp[i-1][j-1];
        else
        {
            dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1],dp[i-1][j-1])) + 1;
            //不理解
        }
    }
}
return dp[word1.size()][word2.size()];
    }
};

?