链接：https://leetcode.com/problems/delete-operation-for-two-strings/
$LCS(Longest\;Common\;Subsequence)$板子题
$Dynamic\;programming$(动态规划)
求出最长公共子序列长度，用两个字符串长度之和减去最长公共子序列长度的两倍即可
很自然地想到动态规划
状态转移方程为 \(dp[j]= \begin{cases} max(dp[j],dp[j-1])&word1[i - 1]\ne word2[j - 1]\\ pre+1 &word1[i - 1] = word2[j - 1]\\ \end{cases}\)
//Time: 24ms Memory: 15.9MB
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.length(), len2 = word2.length(), pre, dp[505];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= len1; ++i)
{
pre = 0;
for(int j = 1; j <= len2; ++j)
{
int h = dp[j];
dp[j] = word1[i - 1] == word2[j - 1] ? pre + 1 : max(dp[j], dp[j - 1]);
pre = h;
}
}
return len1 + len2 - 2 * dp[len2];
}
};