动态规划 Leetcode 72 编辑距离

编辑距离

Leetcode 72

学习记录自代码随想录

要点：1.dp数组定义：dp[i][j]以word1[i-1]结尾时将其转换为word2[0:j-1]需要的最少操作数；
2.递推公式：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, min(dp[i][j-1]+1, dp[i-1][j-1]+1))删除word1[i-1],删除word2[j-1],（插入和删除相同）, 替换
3.dp数组初始化：for(int i = 1; i < m+1; i++) dp[i][0] = i; word1删除i次
for(int j = 1; j < n+1; j++) dp[0][j] = j; word2删除j次

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        // 1.dp[i][j]以word1[i-1]结尾时将其转换为word2[0:j-1]需要的最少操作数
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        // 2.递推公式：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, min(dp[i][j-1]+1, dp[i-1][j-1]+1))删除word1[i-1],删除word2[j-1],（插入和删除相同）, 替换
        // 3.dp数组初始化
        for(int i = 1; i < m+1; i++) dp[i][0] = i;
        for(int j = 1; j < n+1; j++) dp[0][j] = j;
        // 4.遍历顺序：正向遍历
        for(int i = 1; i < m+1; i++){
            for(int j = 1; j < n+1; 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, min(dp[i][j-1] + 1, dp[i-1][j-1] + 1));
                }
            }
        }
        // 5.举例推导dp数组
        return dp[m][n];
    }
};