72.

思路1:直接动规五部曲1、dp数组的含义dp[i][j]表示以i-1和j-1为结尾的两个字符串的最少字符删除个数2、递推公式这里考虑两种情况1、当dp[i-1]dp[j-1]的时候两个元素的是相等的那么这两个元素就不用删所以说dp[i][j]还是等于dp[i-1][j-1]的2、当dp[i-1]!dp[j-1]的时候两个元素不相等这里就要考虑将其中一个元素删除掉如果删除s1[i-1]那么就是dp[i-1][j]1如果删除s2[j-1]那么就是dp[i][j-1]1如果两个都删的话那就是dp[i-1][j-1]23、dp数组的初始化这里由于某个点的值是由其左上角、上方、左方元素得到所以我们初始化的时候一定要初始化第一行和第一列拿第一行为例dp[0][j]也就是s1是空字符串s2非空那么删除的元素个数其实就是j的值第一列也同理4、遍历顺序前面说了由左上方三个元素确定所以一定是左到右上到下遍历5、打印dp数组主要用于debug

代码:

Math.min(dp[i-1][j]1,Math.min(dp[i][j-1]1,dp[i-1][j-1]2));}}}return

dp[m][n];}

(word1.charAt(i-1)word2.charAt(j-1)){dp[i][j]

Math.max(dp[i-1][j],dp[i][j-1]);}}}return

mn-2*dp[m][n];}

正确思路:直接动规五部曲1、dp数组的含义以s1[i-1]结尾的s1和以s2[j-1]结尾的s2怎么操作才可以由s1变到s22、递推公式这里还是涉及两种情况1、s1[i-1]s2[j-1]这种情况下是不需要变元素的所以直接dp[i][j]dp[i-1][j-1]2、s1[i-1]!s2[j-1]这种情况下我们就需要做增删替换了我们可以将s1[i-1]删掉就变成了dp[i-1][j]1将s2[i-1]删掉就变成了dp[i][j-1]1这里其实是可以动s2的因为s1的增相当于s2的删s1的删相当于s2的增还有一种情况是替换的情况我们需要替换一个元素可以达到1的效果那么就是dp[i-1][j-1]13、dp数组初始化这里其实和上一题一样的初始化4、遍历同上5、打印dp数组主要用于debug

代码:

(word1.charAt(i-1)word2.charAt(j-1)){dp[i][j]

Math.min(dp[i-1][j]1,Math.min(dp[i][j-1]1,dp[i-1][j-1]1));}}}return

dp[m][n];}