[数据结构与算法]蓝桥杯零基础冲国赛-第15天

leetcode72
题目描述：
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

思考过程：题中有一个重要解题提示就是三种操作，根据题目描述，一个字符串转另一种字符串可以通过这三种操作。设想word1 = “a”,word2 = “aaaa”,那么就要通过插入操作来转。以其中一个字符串word2为样本，另一种word1的每一位要通过三种操作的其中一种操作来变成word2中相应的字符，所以可以用深搜索来进行列出每一种可能来解题，但是显然深搜的时间复杂度很高。设想现在已经列出所有可能，肯定只有一条可能是符合要求的（也就是操作数最少），所以这涉及到了决策问题，那么就可以用动态规划来解决。因为这道题涉及两个字符串，先认为状态定义数组为dp[n][m]。那么就可以定义状态为dp[i][j]代表以字符串word1 的i位置结尾的字符串转为字符串word2的 j位置结尾的字符串的最少操作数。一般dp[i][j]都是由dp[i - 1][j - 1]转化来的，dp[i - 1][j - 1]转化为dp[i][j]需要通过三种操作中的其中一种。第一种插入操作，就是在第一个字符串的i - 1位置中插入一个字符使字符串和第二个字符串中的i位置相同，那么就是在第一个字符串的i - 1的位置操作一次插入，所以dp[i][j] = dp[i - 1][j] + 1。第二种是删除操作，就是在第二个字符串的j 的位置删除一个字符,使字符串j位置倒退到j - 1位置，所以dp[i][j] = dp[i][j - 1] + 1。第三种就是替换，就是就是在第一个字符串的i位置中替换一个字符使字符串和第二个字符串中的i位置相同，那么就是在第一个字符串的i - 1的位置操作一次替换，所以dp[i][j] = dp[i - 1][j - 1] + 1。边界条件就是当两字符串为空串时的各个最少操作数

解题过程：
状态定义：
dp[i][j]代表以字符串word1 的i位置结尾的字符串转为字符串word2的 j位置结尾的字符串的最少操作数
状态转移：
dp[i][j] = min{dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]} + 1
边界条件：
dp[i][0] = i, dp[0][i] = i;
编码：

int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        int dp[n + 1][m + 1];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
            for (int j = 1; j <= m; 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], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[n][m];
    }

预告：明天超越金典的二分查找