LeetCode 583 Delete Operation for Two Strings
概述
https://leetcode.com/problems/delete-operation-for-two-strings/
动态规划法
极值问题，无脑动态规划。
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), -1));
return helper(dp, word1, word2, 0, 0);
}
int helper(vector<vector<int>>& dp, string& word1, string& word2, int i, int j) {
if (i == word1.size()) return word2.size() - j;
if (j == word2.size()) return word1.size() - i;
if (dp[i][j] != -1) return dp[i][j];
if (word1[i] == word2[j]) {
dp[i][j] = helper(dp, word1, word2, i+1, j+1);
} else {
dp[i][j] = min(1 + helper(dp, word1, word2, i, j + 1), 1 + helper(dp, word1, word2, i + 1, j));
}
return dp[i][j];
}
};