我们先来看题目描述给你两个单词word1和word2 请返回将word1转换成word2所使用的最少操作数 。思路转换过程中的操作如果两个单词某个位置的字符相同可以跳过这一位置不需要额外的操作。如果字符不同则需要进行以下操作之一插入一个字符使 word1 的当前部分匹配 word2 的当前部分。删除一个字符使 word1 的当前部分匹配 word2 的当前部分。替换一个字符将 word1 的当前字符修改为 word2 的当前字符。那么这个时候就得采用动态规划的方式逐步计算从 word1 的前 i 个字符转换为 word2 的前 j 个字符的最小操作数。1. 定义采用二维数组 dp[i][j]它表示将字符串 word1 的前 i 个字符转换为 word2 的前 j 个字符的最少操作数。2. 初始状态当 i 0即 word1 为空字符串时需要插入 j 个字符才能转成 word2 的前 j 个字符dp[0][j] j当 j 0即 word2 为空字符串时需要删除 i 个字符才能将 word1 变为空字符串dp[i][0] i3. 状态转移分析对于任意 i 0, j 0 则考虑 word1[i-1] 和 word2[j-1] 是否相同如果相同word1[i-1] word2[j-1]无需操作结果等于转换前 i-1 个字符和 j-1 个字符的结果。dp[i][j] dp[i-1][j-1]如果不同word1[i-1]! word2[j-1]此时就需要选择插入、删除和替换的最优解dp[i][j] min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1])dp[i-1][j]对应删除操作表示删除word1的当前字符dp[i][j-1]对应插入操作表示在word1的当前追加最后一个字符dp[i-1][j-1]对应替换操作表示将当前字符替换为目标字符。具体代码如下int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(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] 1 min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}); } } } return dp[m][n]; }时间复杂度O(m*n)空间复杂度O(m*n)好了本文到这里就结束了希望认真阅读全文的小伙伴都能有所收获哦