1、目前动态规划的子序列系列的题目之间的区别与联系【力扣300.最长递增子序列】一个数组不连续【力扣674.最长连续递增子序列】一个数组连续【力扣718.最长重复子数组】两个数组连续【力扣1143.最长公共子序列】两个数组不连续【力扣1035.不相交的线】与1143本质一样两个数组不连续【力扣53.最大子数组和】一个数组连续【力扣392.判断子序列】与1143本质一样两个数组不连续【力扣115.不同的子序列】与1143本质一样两个数组不连续【力扣583.两个字符串的删除操作】与1143本质一样两个数组不连续本题【力扣72.编辑距离】与1143本质一样两个数组不连续本题在上一题583的基础上多了其他操作2、关键区别本题是前面的题目的综合题涉及了数组的增、删、改代码体现在递推公式上// 分析一下本题的递推公式// 如果word1[i-1] word2[j-1]说明不用操作回看dp数组的定义需要计算的是最少操作数// 所以如果word1[i-1] word2[j-1]那么dp[i][j] dp[i-1][j-1];dp[i][j]不做任何操作// 如果word1[i-1] 不等于 word2[j-1]那么也就是说当前两个指针所指元素不一样的时候。删除第一个数组的当前元素也就是第一个指针回退或者删除第二个数组的当前元素也就是第二个指针回退因为增加元素的操作就是删除元素的逆操作所以只增加较少元素数组的最少操作数和只删除较多元素数组的最少操作数是一样的所以不考虑增加元素的情况或者两个元素替换一下因为替换第一个数组的元素使得第一个数组与第二个数组相同的操作和替换第二个数组的元素使得第二个数组与第一个数组相同的操作是一样的所以只操作一次就好// 如果word1[i-1] 不等于 word2[j-1]dp[i][j]的值可能来源于上面三种情况取最小值就行。也就是说dp[i][j] min(min(dp[i-1][j]1,dp[i][j-1]1),dp[i-1][j-1]1); // 删除了第一个数组的当前元素其实算是操作了一次所以dp[i-1][j]要加1比如例1两个数组的元素是假设的比如例2两个数组的元素是假设的以上三种情况都是在word1[i-1] 不等于 word2[j-1]的时候dp[i][j]的可能来源最小的操作数就是当前dp[i][j]的实际来源【代码如下图所示】