重庆市建设工程信息网官网安全监督渝快办seo查询平台

动态规划

• 思路：
  • 假设 dp[i][j] 是 word1 前 i 个字母到 word2 前 j 个字母的编辑距离；
  • 那么状态 dp[i][j] 状态的上一个状态有：
    • dp[i - 1][j]，word1 前 i - 1 个字母到 word2 前 j 个字母的编辑距离，此状态再插入一个字母就迁移到 dp[i][j] 状态；
    • 同理在 dp[i][j - 1] 状态 word2 插入一个字母就迁移到 dp[i][j]；
    • 状态 dp[i - 1][j - 1]，如果 word1 和 word2 最后一个字母相同，则不需要替换；否则，需要进行替换，增加一次编辑；
  • dp[i][j] 是这个上一状态迁移所需距离最小的值；
  • 同时，当一个字母为空串时，需要编辑的距离为另外一个字母的长度：
    • dp[0][j] = j
    • dp[i][0] = i

class Solution {
public:int minDistance(string word1, string word2) {int sz1 = word1.size();int sz2 = word2.size();if (sz1 == 0) {return sz2;}if (sz2 == 0) {return sz1;}std::vector<std::vector<int>> dp(sz1 + 1, std::vector<int>(sz2 + 1));// if word2 emptyfor (int i = 0; i <= sz1; ++i) {dp[i][0] = i;}// if word1 emptyfor (int j = 0; j <= sz2; ++j) {dp[0][j] = j;}for (int i = 1; i <= sz1; ++i) {for (int j = 1; j <= sz2; ++j) {int dp_add = dp[i - 1][j] + 1;int dp_del = dp[i][j - 1] + 1;int dp_re = dp[i - 1][j - 1];if (word1[i - 1] != word2[j - 1]) {dp_re += 1;}dp[i][j] = std::min(std::min(dp_add, dp_del), dp_re);}}return dp[sz1][sz2];}
};