Created 02/05/2020 at 03:26PM

记录动态规划值得收藏的题目

leetcode T.72

题目

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作:

题解

int minDistance(string word1, string word2) {
    map<pair<int, int>, int> dp;
    size_t m = word1.size();
    size_t n = word2.size();
    if (!(m*n)) {
        return max(m, n);
    }
    for (int i = 0; i < m + 1; i++) { dp[make_pair(i, 0)] = i; }
    for (int i = 0; i < n + 1; i++) { dp[make_pair(0, i)] = i; }
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[make_pair(i, j)] = min(dp[make_pair(i - 1, j)] + 1, dp[make_pair(i, j - 1)] + 1);
                dp[make_pair(i, j)] = min(dp[make_pair(i, j)], dp[make_pair(i - 1, j - 1)]);
            }
            else {
                dp[make_pair(i, j)] = min(dp[make_pair(i - 1, j)] + 1, dp[make_pair(i, j - 1)] + 1);
                dp[make_pair(i, j)] = min(dp[make_pair(i, j)], dp[make_pair(i - 1, j - 1)] + 1);
            }
        }
    }
    return dp[make_pair(m, n)];
}