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

文章总结：代码随想录

视频总结：动态规划之子序列，还是为了编辑距离做铺垫 | LeetCode：583.两个字符串的删除操作_哔哩哔哩_bilibili

力扣题目：LeetCode 583.两个字符串的删除操作

动态规划五步曲：

1.确定dp[i][j]的含义

dp[i][j]:遍历到下标为i且下标为j的时候所需要的最小步数为dp[i][j]

2.找出递推公式

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]+2, Math.min(dp[i-1][j]+1, dp[i][j-1]+1));
}

3.初始化dp数组

for(int i = 0; i < word1.length()+1; i++)   dp[i][0] = i;
for(int j = 0; j < word2.length()+1; j++)   dp[0][j] = j;

4.确定遍历方向

从左往右，从上往下遍历

5.打印dp数组

代码如下（Java）：

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

LeetCode 72.编辑距离

文章总结：代码随想录

视频总结：动态规划终极绝杀！ LeetCode：72.编辑距离_哔哩哔哩_bilibili

力扣题目：LeetCode 72.编辑距离

动态规划五步曲：

1.确定dp[i][j]的含义

dp[i][j]:遍历下标为i且下标为j的时候所得到的最小操作数为dp[i][j]

2.找出递推公式

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-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
}

3.初始化dp数组

for(int i = 1; i <= m; i++) dp[i][0] = i;
for(int j = 1; j <= n; j++) dp[0][j] = j;

4.确定遍历方向

从左往右，从上往下遍历

5.打印dp数组

代码如下（Java）：

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++) dp[i][0] = i;for(int j = 1; 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(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;}}}return dp[m][n];}
}