leetcode 72 编辑距离

动态规划

• 确定dp数组以及下标的含义
  dp[i][j] 表示前 i 个字符的word1，和前 j 个字符的word2，最近编辑距离。
• 递推公式
• if (word1[ i ] == word2[ j ]) 那么说明不用任何编辑，
  即dp[i+1][j+1] = dp[i ][j ];
• if (word1[ i ] ！= word2[ j ]) 有三种情况

删除world1

word1第 i 个字符删除一个元素，就是world1第 i -1 与world2第 j 再加上一个操作。

即 dp[i+1][j+1] = dp[ i ][ j+1] + 1;

删除world2（相当于添加world1）

word2第 j 个字符删除一个元素，就是world1第 i 与world2第 j -1 再加上一个操作。

即 dp[i+1][j+1] = dp[ i +1][ j] + 1;

替换元素

word1第 i 个字符和word1第 i -1个字符替换，world2同样，就是world1第 i -1 与world2第 j -1 再加上一个操作。

即 dp[i+1][j+1] = dp[ i ][ j] + 1;

最终三种情况取最小

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

dp数组初始化

• dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
  那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;
  
• 同理dp[0][j] = j;
  

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1));
        for(int i=0 ; i<word1.size();i++)
            dp[i+1][0] = i+1;
        for(int j=0 ; j<word2.size();j++)
            dp[0][j+1] = j+1;
        for(int i=0;i<word1.size();i++)
        {
            for(int j=0; j<word2.size();j++)
            {
                if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];
                else dp[i+1][j+1] = min( dp[i][j] , min(dp[i][j+1],dp[i+1][j])) + 1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

二刷

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1 , vector<int>(word2.size()+1 , 0) );
        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-1]+1 , min( dp[i-1][j]+1,dp[i][j-1]+1 ) );
                // cout<<dp[i][j]<<' ';
            }
            // cout<<endl;
        }
        return  dp[word1.size()][word2.size()];
    }
};