583.两个字符串的删除操作
题目
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
提示：
给定单词的长度不超过500。
给定单词中的字符只含有小写字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
一般删除操作很少做，因为删除之后字符的位置改变了，是很麻烦的。所以这道题应该可以做转换。
删除之后相对位置是没有变的,找到 word1 和 word2 相同。这个不就是之前的最长公共子序列吗？
那么这道题可以转化为求最长公共子序列的长度，删除的=总的-最长公共子序列的长度*2
定义dp数组及其下边的含义
dp[i][j]表示以[i-1]结尾的字符串1与以[j-1]结尾的字符串2之间的最长公共子序列的长度为dp[i][j]
dp数组递推式
如果word1[i-1] == word2[j-1]，说明当前两个字符可以接上之前的最长公共子序列构成新的最长公共子序列，那么长度肯定是之前的+1，dp[i][j] = dp[i-1][j-1] + 1
如果word1[i-1] ≠ word2[j-1],有两种路径可以达到，i从i-2往前走一步，或者j从j-2往前走一步，为什么不两个同时走一步？因为虽然word1[i-1] ≠ word2[j-1]，但是可能word1[i-1] == word2[j-2]，如果两个同时不看就会漏掉这种情况。
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
dp数组初始化
i=0和j=0时在本题时没有意义的，初始化为0即可，这里采用类的成员函数默认初始化值不显示初始化
遍历顺序
int len1=word1.length();
int len2=word2.length();
if(len1==0) return len2;
if(len2==0) return len1;
int dp [] [] = new int [len1+1][len2+1];
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return len1+len2-dp[len1][len2];
空间优化
还是老思路
dp[i][j]只与dp[i-1][j-1]、dp[i-1]、dp[i][j-1]有关。
如果我们压缩成一维数组，
dp([i])[j] = dp([i-1])[j-1] + 1
执行dp([i])[j] = Math.max(dp([i-1])[j],dp([i])[j-1])时，发现dp([i])[j-1]和上面dp([i-1])[j-1]表示都是dp[j-1],那这里取得是相同值，肯定是不行的，按执行的顺序i会比i-1后执行，那么此处dp[j-1]保存的是dp([i])[j-1]的值，所以我们需要在i-1的时候保存dp[i-1][j-1]的值
int len1=word1.length();
int len2=word2.length();
if(len1==0) return len2;
if(len2==0) return len1;
int dp [] = new int[len2+1];
int tmp = 0;
int last;
for(int i=1;i<len1;i++){
last = dp[0];//每次循环需要归位,不然使用的就是结尾的左对角线
for(int j=1;j<len2;j++){
tmp = dp[j]; //保存的是dp[i-1][j]
if(word1.charAt(i-1)==word2.charAt(j-1))
//dp[i][j] = dp[i-1][j-1] + 1;
//dp[j] = dp[j-1] + 1;
dp[j] = last + 1;
//else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
else dp[j] = Math.max(dp[j],dp[j-1]);
last = tmp; //对下一次循环(下一次j本次是j-1)的last来说dp[i-1][j-1]
}
}