编辑距离
72. 编辑距离 - 力扣（LeetCode）
动态规划：
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：
1. 初始化：将 `dp[0][j]` 和 `dp[i][0]` 初始化为相应的初始值。`dp[0][j]` 表示将空字符串转换为 `word2` 的前 `j` 个字符所需的最小编辑距离，即插入操作。同理，`dp[i][0]` 表示将 `word1` 的前 `i` 个字符转换为空字符串所需的最小编辑距离，即删除操作。
2. 状态转移：对于 `dp[i][j]`，考虑 `word1` 的第 `i` 个字符和 `word2` 的第 `j` 个字符：
- 如果 `word1.charAt(i - 1) == word2.charAt(j - 1)`，说明当前字符相同，不需要进行操作，所以 `dp[i][j] = dp[i - 1][j - 1]`。
- 如果 `word1.charAt(i - 1) != word2.charAt(j - 1)`，说明当前字符不同，此时有三种操作可选：
1. 替换：`dp[i - 1][j - 1] + 1`
2. 插入：`dp[i][j - 1] + 1`
3. 删除：`dp[i - 1][j] + 1` 取这三种操作的最小值，并加上对应的操作次数。
3. 结果：最终的最小编辑距离存储在 `dp[n1][n2]` 中，其中 `n1` 是 `word1` 的长度，`n2` 是 `word2` 的长度。
class Solution { public int minDistance(String word1, String word2) { int n1 = word1.length(); int n2 = word2.length(); // 为了处理第 0 行第 0 列空字符串的情况 int[][] dp = new int[n1 + 1][n2 + 1]; // 第一行 for (int j = 1; j <= n2; j++){ dp[0][j] = dp[0][j - 1] + 1; } // 第一列 for (int i = 1; i <= n1; i++) { dp[i][0] = dp[i - 1][0] + 1; } for (int i = 1; i <= n1; i++) { for (int j = 1; j <= n2; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { // 记得Math.min函数只接受两个参数，所以要放两个 dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;} } } return dp[n1][n2]; } }最长公共子序列
1143. 最长公共子序列 - 力扣（LeetCode）
和 编辑距离 同为经典的双字符串动态规划问题。用两个指针 `i, j` 在两个字符串上游走，这就是「状态」，字符串中的每个字符都有两种「选择」，要么在 `lcs` 中，要么不在。
`dp[i][j]` 的含义是：对于 `s1[1..i]` 和 `s2[1..j]`，它们的 LCS 长度是 `dp[i][j]`
class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 实际上要从 0 开始， 所以要-1 if (text1.charAt(i - 1) == text2.charAt(j - 1)) { // text1[i - 1] 和 text2[j - 1] 必然在lcs中 dp[i][j] = dp[i - 1][j - 1] + 1; } else { // text1[i - 1] 和 text2[j - 1] 至少有一个不在lcs中 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } }