力扣72. 编辑距离
动态规划
- 思路：
- 假设 dp[i][j] 是 word1 长度 i 和 word2 长度 j 的编辑距离；
- 有三种编辑方式：插入、删除、替换，即 word1 插入、word2 插入、替换；
- 那么 dp[i][j] 可以是：
- dp[i - 1][j] 在 word1 中插入一个字符；
- dp[i][j - 1] 在 word2 中插入一个字符；
- dp[i - 1][j - 1] 如果 word1[i - 1] == word2[j - 1]（word1 的第 i 个字符与 word2 的第 j 个字符相等）那么 dp[i][j] = dp[i - 1][j - 1]，否则需要进行一次替换；
- dp[i][j] 选择三种编辑中距离最小的即可；
- 边界条件：
- dp[i][0] = i （word2 插入 i 次）
- dp[0][j] = j （word1 插入 i 次）
class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size();int n = word2.size();if (m * n == 0) {return m + n;}std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));for (int i = 0; i < m + 1; ++i) {dp[i][0] = i;}for (int j = 0; j < n + 1; ++j) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; ++j) {int dp1 = dp[i - 1][j] + 1;int dp2 = dp[i][j - 1] + 1;int dp3 = dp[i - 1][j - 1];if (word1[i - 1] != word2[j - 1]) {dp3 += 1;}dp[i][j] = std::min(dp1, std::min(dp2, dp3));}}return dp[m][n];}
};——————————————————————————————————
