力扣爆刷第133天之动态规划收尾（距离编辑与回文子串）

力扣爆刷第133天之动态规划收尾（距离编辑与回文子串）

文章目录

• • • 力扣爆刷第133天之动态规划收尾（距离编辑与回文子串）
    • 一、72. 编辑距离
    • 二、647. 回文子串
    • 三、516. 最长回文子序列

      一、72. 编辑距离

      题目链接：https://leetcode.cn/problems/edit-distance/description/

      
      （图片来源网络，侵删）

      思路：本题也是前面重复子序列的变体，可以对字符串进行增删替换操作，其中增加和删除是一样的，而替换依赖的是前一个位置。

      定义dp[i][j]表示以下标i为结尾的word1和以下标j为结尾的word2要相等所需要的操作。

      如果word1[i] == word2[j]，那么所需次数依赖于word1[i-1]和word2[j-1]，即dp[i][j] = dp[i-1][j-1]。

      如果word1[i] != word2[j]，那么增删对应的都是dp[i-1][j]，dp[i][j-1]，替换对应的是dp[i-1][j-1]，取三者最低。

      class Solution {
          public int minDistance(String word1, String word2) {
              int m = word1.length(), n = word2.length();
              int[][] dp = new int[m+1][n+1];
              for(int i = 0; i 
                  for(int j = 0; j