代码随想录第五十六天

Leetcode 583. 两个字符串的删除操作

题目链接: 两个字符串的删除操作
自己的思路:想到了，但是初始化初始错了！！！！

思路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]+2；3、dp数组的初始化：这里由于某个点的值，是由其左上角、上方、左方元素得到，所以我们初始化的时候一定要初始化第一行和第一列，拿第一行为例，dp[0][j]，也就是s1是空字符串，s2非空，那么删除的元素个数其实就是j的值，第一列也同理；4、遍历顺序：前面说了，由左上方三个元素确定，所以一定是左到右，上到下遍历；5、打印dp数组：主要用于debug！！！！！

代码:

class Solution {public int minDistance(String word1, String word2) {char[] c1 = word1.toCharArray();char[] c2 = word2.toCharArray();int m = c1.length;int n = c2.length;int[][] dp = new int[m+1][n+1];for (int i =0;i<=m;i++){dp[i][0] = i;}for (int i =0;i<=n;i++){dp[0][i] = i;}dp[0][0]=0;for (int i =1;i<=m;i++){for (int j=1;j<=n;j++){//递推公式if (c1[i-1]==c2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+2));}}}return dp[m][n];}
}

思路2:最长公共子序列的思路！！！

代码:

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m+1][n+1];for (int i =1;i<=m;i++){for (int j=1;j<=n;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 m+n-2*dp[m][n];}
}

Leetcode 72. 编辑距离

题目链接: 编辑距离
自己的思路:思路差不多，只是没调出来！！！！

正确思路:直接动规五部曲：1、dp数组的含义：以s1[i-1]结尾的s1和以s2[j-1]结尾的s2，怎么操作才可以由s1变到s2；2、递推公式：这里还是涉及两种情况：（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]+1；3、dp数组初始化：这里其实和上一题一样的初始化；4、遍历：同上；5、打印dp数组：主要用于debug！！！！

代码:

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m+1][n+1];//初始化for (int i =0;i<=m;i++){dp[i][0] = i;}for (int j=0;j<=n;j++){dp[0][j] = j;}for (int i =1;i<=m;i++){for (int j=1;j<=n;j++){//递推公式if (word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{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];}
}