今天是第五十六天,是距离问题的动态规划
class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n+1][m+1]; for(int i =1; i<=n ;i++){ for(int j = 1; j<=m; 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][j-1],dp[i-1][j]); } } } return m + n - dp[n][m]*2; } }
dp的数组存储公共的部分,那么其他的部分就是总长减去每个字符串相同的部分,就是不同的,需要删除的部分了。
class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][]dp = new int[n+1][m+1]; for(int i = 1; i<=n; i++){ dp[i][0] = dp[i-1][0]+1; } for(int j = 1; j<=m; j++){ dp[0][j] = dp[0][j-1]+1; } for(int i = 1; i<=n; i++){ for(int j = 1; j<=m; j++){ if(word1.charAt(i-1) == word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; } else{ dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1])+1; } } } return dp[n][m]; } }
和上一道题很像,这个dp是记录最小删除次数的。
今天的题是路径删除问题,沿用的依旧是dp数组的模版
标签:String,int,训练营,随想录,length,word1,word2,第五十六,dp From: https://www.cnblogs.com/catSoda/p/16965071.html