```
int minDistance(string word1, string word2) {
const auto M = word1.size();
const auto N = word2.size();
vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
for (auto i = 1; i <= M; i++) {
for (auto j = 1; j <= N; j++) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
if (word1[i-1] == word2[j-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
}
}
}
return M + N - dp[M][N] * 2;
}
```