【算法训练-动态规划三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离-阿里云开发者社区

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【】，使用【】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

最长重复子数组【MID】

线性DP问题再搞一道，最长重复子数组

题干

解题思路

原题解地址：A 、B数组各抽出一个前缀数组，单看它们的末尾项：

如果它们俩不一样，则公共子数组肯定不包括它们俩。
如果它们俩一样，则要考虑它们俩前面的子数组「能为它们俩提供多大的公共长度」。

继续向前递推的：

如果它们俩的前缀数组的「末尾项」不相同，由于子数组的连续性，前缀数组不能为它们俩提供公共长度
如果它们俩的前缀数组的「末尾项」相同，则可以为它们俩提供公共长度：至于提供多长的公共长度？这又取决于前缀数组的末尾项是否相同……

存在重复子问题和递推的方法，可以用动态规划解决。回到题目，A 、B数组各抽出一个前缀子数组，单看它们的末尾项

如果它们俩不一样——以它们俩为末尾项形成的公共子数组的长度为0：dp[i][j] = 0
如果它们俩一样，以它们俩为末尾项的公共子数组，长度保底为1——dp[i][j]至少为 1，要考虑它们俩的前缀数组——dp[i-1][j-1]能为它们俩提供多大的公共长度

继续向前递推：

如果它们俩的前缀数组的「末尾项」不相同，前缀数组提供的公共长度为 0——dp[i-1][j-1] = 0，以它们俩为末尾项的公共子数组的长度——dp[i][j] = 1
如果它们俩的前缀数组的「末尾项」相同，前缀部分能提供的公共长度——dp[i-1][j-1]，它至少为 1，以它们俩为末尾项的公共子数组的长度 dp[i][j] = dp[i-1][j-1] + 1

题目求：最长公共子数组的长度。不同的公共子数组的末尾项不一样。我们考察不同末尾项的公共子数组，找出最长的那个。

1 定义状态（定义子问题）

我们定义dp[i][j]标识：长度为i，末尾项为A[i-1]的子数组，与长度为j，末尾项为B[j-1]的子数组，二者的最大公共后缀子数组长度

2 定义状态转移方程

dp[i][j] ：长度为i，末尾项为A[i-1]的子数组，与长度为j，末尾项为B[j-1]的子数组，二者的最大公共后缀子数组长度。

如果 A[i-1] != B[j-1]，有 dp[i][j] = 0
如果 A[i-1] == B[j-1] ，有 dp[i][j] = dp[i-1][j-1] + 1

3 初始化状态

为了不判断边界条件，我们给DP Table补0，所以base case：如果i==0||j==0，则二者没有公共部分，dp[i][j]=0

4 求解方向

这里采用自底向上，从最小的状态开始求解

5 找到最终解

最长公共子数组以哪一项为末尾项都有可能，求出每个 dp[i][j]，找出最大值。

代码实现

给出代码实现基本档案

基本数据结构：数组

辅助数据结构：无

算法：动态规划

技巧：无

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int findLength(int[] nums1, int[] nums2) {
        // 1 入参异常校验
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return 0;
        }
        // 2 定义dp数组，dp[i][j] 表示以nums1中以i-1结尾的元素与nums2中以j-1结尾的元素最长重复子数组
        int rows = nums1.length;
        int cols = nums2.length;
        // base case dp[0][0]=0,初始化第一行第一列为0
        int[][] dp = new int[rows + 1][cols + 1];
        // 3 状态转移方程
        int ans = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                // 如果以i-1,j-1为结尾的元素相等，则至少重复子数组长度+1，并比较大小
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 设置值的过程中更新最大值
                    ans = Math.max(ans, dp[i][j]);
                } else {
                    // 如果以i-1,j-1为结尾的元素不相等，则无重复子数组，长度归0
                    dp[i][j] = 0;
                }
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(N*M)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；

空间复杂度：O(N*M)，DP数组是二维数组

最长公共子串【MID】

首先来一道最长公共子串，难度还没有升级，公共字符是连续的即可

题干

解题思路

求两个数组或者字符串的最长公共子序列问题，肯定是要用动态规划的。

首先，区分两个概念：子序列可以是不连续的；子数组（子字符串）需要是连续的；
另外，单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

1. 状态定义

对于本题而言，可以定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。（注：text1[0:i-1] 表示的是 text1 的第 0 个元素到第 i - 1 个元素，两端都包含）之所以 dp[i][j] 的定义不是 text1[0:i] 和 text[0:j] ，是为了方便当 i = 0 或者 j = 0 的时候，dp[i][j]表示空字符串和另外一个字符串的匹配，这样 dp[i][j] 可以初始化为空字符串

2. 状态转移方程

知道状态定义之后，开始写状态转移方程。

当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子串长度又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + text1[i]；
当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，所以不够成公共子串，不满足条件

综上状态转移方程为：

dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1), 当 text1[i−1]==text2[j−1]

当然我们还需要当前最新下标来辅助记录子串最新的更新位置

3. 状态的初始化

初始化就是要看当 i = 0 与 j = 0 时， dp[i][j] 应该取值为多少。

当 i = 0 时，dp[0][j] 表示的是 text1中取空字符串跟 text2的最长公共子序列，结果肯定为空字符串.
当 j = 0 时，dp[i][0] 表示的是 text2中取空字符串跟 text1的最长公共子序列，结果肯定为空字符串.

综上，当 i = 0 或者 j = 0 时，dp[i][j] 初始化为空字符串.

4. 遍历方向与范围

由于 dp[i][j] 依赖于 dp[i - 1][j - 1] ,，所以 i和 j的遍历顺序肯定是从小到大（自底向上）的。另外，由于当 i和 j 取值为 0 的时候，dp[i][j] = 0，而 dp 数组本身初始化就是为空字符串，所以，直接让 i 和 j 从 1 开始遍历。遍历的结束应该是字符串的长度为 len(text1)和 len(text2)。

5. 最终返回结果

由于 dp[i][j] 的含义是 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。我们最终希望求的是 text1 和 text2 的最长公共子序列。所以需要返回的结果是 i = len(text1) 并且 j = len(text2) 时的 dp[len(text1)][len(text2)]。

代码实现

给出代码实现基本档案

基本数据结构：字符串

辅助数据结构：无

算法：动态规划

技巧：无

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // 入参条件判断
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 1) {
            return null;
        }
        // 1 初始化状态
        int ls1 = str1.length();
        int ls2 = str2.length();
        // dp表示范围为0-ls1的str1与0-ls2的str2的最长公共子串长度
        int[][] dp = new int[ls1 + 1][ls2 + 1];
        int max = 0;
        int latestIndex = 0;
        // 2 遍历（自底向上）
        for (int i = 1; i <= ls1; i++) {
            for (int j = 1; j <= ls2; j++) {
                // 状态转移方程
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 更新子串最大长度以及当前子串下标
                    if (dp[i][j] > max) {
                        max = dp[i][j];
                        // 公共子串不包含latestIndex位置
                        latestIndex = i;
                    }
                }
            }
        }
        // 上述循环i从1开始，这里subString右侧为开区间，刚好适用
        return str1.substring(latestIndex - max, latestIndex);
    }
}

复杂度分析

时间复杂度：O(n^2 )，构造辅助数组dp与b，两层循环，递归是有方向的递归，因此只是相当于遍历了二维数组

空间复杂度：O(n^2 )，辅助二维数组dp与递归栈的空间最大为O(n^2 )

最长公共子序列【MID】

难度升级，明确下什么是公共子序列。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，ace是 abcde的子序列，但 aec不是 abcde 的子序列

题干

解题思路

求两个数组或者字符串的最长公共子序列问题，肯定是要用动态规划的。

首先，区分两个概念：子序列可以是不连续的；子数组（子字符串）需要是连续的；
另外，单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

1. 状态定义

2. 状态转移方程

知道状态定义之后，开始写状态转移方程。

当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + text1[i]；举个例子，比如对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + text[1] = c。
当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比如对于 ace 和 bc 而言，他们的最长公共子序列等于 ① ace 和 b 的最长公共子序列:空字符串的长度0 与 ② ac 和 bc 的最长公共子序列c长度1 的最大值，即 1，所以选择长度大的

综上状态转移方程为：

dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1), 当 text1[i−1]==text2[j−1]
dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];, 当 text1[i−1]!=text2[j−1]

3. 状态的初始化

初始化就是要看当 i = 0 与 j = 0 时， dp[i][j] 应该取值为多少。

当 i = 0 时，dp[0][j] 表示的是 text1中取空字符串跟 text2的最长公共子序列，结果肯定为空字符串.
当 j = 0 时，dp[i][0] 表示的是 text2中取空字符串跟 text1的最长公共子序列，结果肯定为空字符串.

综上，当 i = 0 或者 j = 0 时，dp[i][j] 初始化为空字符串.

4. 遍历方向与范围

5. 最终返回结果

代码实现

给出代码实现基本档案

基本数据结构：字符串

辅助数据结构：无

算法：动态规划

技巧：无

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // 0 入参校验
        if (s1 == null || s1.length() == 0 || s2 == null ||
                s2.length() == 0) return "-1";
        // 1 状态定义及初始化
        int ls1 = s1.length();
        int ls2 = s2.length();
        // 长度为ls1和长度为ls2的最长公共子序列是dp
        String[][] dp = new String[ls1 + 1][ls2 + 1];
        // 2 初始化状态值，当初始化状态时，公共子序列为空字符串
        for (int i = 0; i <= ls1; i++) {
            // j为0表示一个长度不为0的s1和一个长度永远为0的字符串公共子序列一定是空字符串
            dp[i][0] = "";
        }
        for (int j = 0; j <= ls2; j++) {
            // i为0表示一个长度不为0的s1和一个长度永远为0的字符串公共子序列一定是空字符串
            dp[0][j] = "";
        }
        // 3 自底向上遍历
        for (int i = 1; i <= ls1; i++) {
            for (int j = 1; j <= ls2; j++) {
                // 4 状态转移方程
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    // 如果s1和s2的字符相等，dp[1][1]表示dp[0][0]+a=a(自底向上)
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
                } else {
                    // 如果s1和s2的字符不相等，取dp[i - 1][j]和dp[i][j - 1]较长的字符作为dp[i][j]
                    dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] :
                               dp[i][j - 1];
                }
            }
        }
        // 5 返回的是两个完整s1和s2的公共子序列
        return dp[ls1][ls2] == "" ? "-1" : dp[ls1][ls2];
    }
}

复杂度分析

时间复杂度：O(n^2 )，构造辅助数组dp与b，两层循环，递归是有方向的递归，因此只是相当于遍历了二维数组

空间复杂度：O(n^2 )，辅助二维数组dp与递归栈的空间最大为O(n^2 )

编辑距离【HARD】

终于又来到一道看了很久的高频题目这里

题干

搞定了一系列的简单题，来个编辑距离练练手

解题思路

原题解地址，解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前移动，缩小问题的规模

设两个字符串分别为 rad 和 apple，为了把 s1 变成 s2，算法会这样进行

暴力递归

base case 是 i 走完 s1 或 j 走完 s2，可以直接返回另一个字符串剩下的长度。对于每对儿字符 s1[i] 和 s2[j]，可以有四种操作：

if s1[i] == s2[j]:
    啥都别做（skip）
    i, j 同时向前移动
else:
    三选一：
        插入（insert）
        删除（delete）
        替换（replace）

有这个框架，问题就已经解决了。读者也许会问，这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // i，j 初始化指向最后一个索引
    return dp(s1, m - 1, s2, n - 1);
}
// 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
int dp(String s1, int i, String s2, int j) {
    // base case
    if (i == -1) return j + 1;
    if (j == -1) return i + 1;
    if (s1.charAt(i) == s2.charAt(j)) {
        return dp(s1, i - 1, s2, j - 1); // 啥都不做
    }
    return min(
        dp(s1, i, s2, j - 1) + 1,    // 插入
        dp(s1, i - 1, s2, j) + 1,    // 删除
        dp(s1, i - 1, s2, j - 1) + 1 // 替换
    );
}
int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

情况一：什么都不做

if s1[i] == s2[j]:
    return dp(s1, i - 1, s2, j - 1); # 啥都不做
# 解释：
# 本来就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)

如果 s1[i] != s2[j]，就要对三个操作递归了

情况二：插入操作

dp(s1, i, s2, j - 1) + 1,    # 插入
# 解释：
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
# 别忘了操作数加一

插入操作

情况三：删除操作

dp(s1, i - 1, s2, j) + 1,    # 删除
# 解释：
# 我直接把 s[i] 这个字符删掉
# 前移 i，继续跟 j 对比
# 操作数加一

情况四：替换操作

dp(s1, i - 1, s2, j - 1) + 1 # 替换
# 解释：
# 我直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
# 同时前移 i，j 继续对比
# 操作数加一

a字符被替换为p字符

int dp(i, j) {
    dp(i - 1, j - 1); // #1
    dp(i, j - 1);     // #2
    dp(i - 1, j);     // #3
}

对于子问题 dp(i-1, j-1)，如何通过原问题 dp(i, j) 得到呢？有不止一条路径，比如 dp(i, j) -> #1 和 dp(i, j) -> #2 -> #3。一旦发现一条重复路径，就说明存在巨量重复路径，也就是重叠子问题

动态规划

接下来用DP table来优化一下，降低重复子问题，首先明确 dp 数组的含义，dp 数组是一个二维数组，长这样

有了之前递归解法的铺垫，应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base case，dp[i][j] 的含义和之前的 dp 函数类似

替换操作：word1的0~i-1位置与word2的0~j-1位置的字符都相同,只是当前位置的字符不匹配,进行替换操作后两者变得相同dp[i-1][j-1] 表示需要进行替换操作才能转到dp[i][j]，所以此时dp[i][j]=dp[i-1][j-1]+1(这个加1代表执行替换操作)
删除操作: 若此时word1的0~i-1位置与word2的0~j位置已经匹配了,此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)和word2的0~j位置匹配,因此此时dp[i][j]=dp[i-1][j]+1(这个加1代表执行删除操作)
插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配，此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,所以此时dp[i][j]=dp[i][j-1]+1(这个加1代表执行插入操作)

有了之前递归解法的铺垫，应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base case，dp[i][j] 的含义和之前的 dp 函数类似

int dp(String s1, int i, String s2, int j)
// 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离

dp 函数的 base case 是 i, j 等于 -1，而数组索引至少是 0，所以 dp 数组会偏移一位

dp[i-1][j-1]
// 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离

既然 dp 数组和递归 dp 函数含义一样，也就可以直接套用之前的思路写代码，唯一不同的是，DP table 是自底向上求解，递归解法是自顶向下求解

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]
    int[][] dp = new int[m + 1][n + 1];
    // base case 
    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 (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min(
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
}
int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

代码实现

给出代码实现基本档案

基本数据结构：数组

辅助数据结构：无

算法：动态规划

技巧：无

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Solution
{
    // 编辑距离，返回两个字符串操作的最小距离
    public int minDistance(String word1, String word2)
    {
        // 1 入参校验
        if(word1.length() < 1 && word2.length() < 1)
        {
            return 0;
        }
        // 2 定义行列长度，word1作为竖，word2作为行
        int m = word1.length();
        int n = word2.length();
        // 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]
        int[][] dp = new int[m + 1][n + 1];
        // 4 初始化base case
        for(int i = 1; i <= m; i++)
        {
            dp[i][0] = i;
        }
        for(int j = 1; j <= n; j++)
        {
            dp[0][j] = j;
        }
        // 5 状态转移方程:自底向上求解，从头开始比较，i=0和j=0的位置初始化为基本操作数
        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] = minCompare(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }
    private int minCompare(int a, int b, int c)
    {
        return Math.min(a, Math.min(b, c));
    }
}

第一行，是 word1 为空，变成 word2 最少步数，就是插入操作
第一列，是 word2 为空，word1要变为word2(也就是空)需要的最少步数，就是删除操作

(一)、当word1[i]==word2[j]时,由于遍历到了i和j,说明word1的0~i-1和word2的0~j-1的匹配结果已经生成,
由于当前两个字符相同,因此无需做任何操作,dp[i][j]=dp[i-1][j-1]
(二)、当word1[i]!=word2[j]时,可以进行的操作有3个:
      ① 替换操作:可能word1的0~i-1位置与word2的0~j-1位置的字符都相同,
           只是当前位置的字符不匹配,进行替换操作后两者变得相同,
           所以此时dp[i][j]=dp[i-1][j-1]+1(这个加1代表执行替换操作)
      ②删除操作:若此时word1的0~i-1位置与word2的0~j位置已经匹配了,
         此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)
         和word2的0~j位置匹配,因此此时dp[i][j]=dp[i-1][j]+1(这个加1代表执行删除操作)
      ③插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配,
          此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得
          此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,
          所以此时dp[i][j]=dp[i][j-1]+1(这个加1代表执行插入操作)
      ④由于题目所要求的是要最少的操作数:所以当word1[i] != word2[j] 时,
          需要在这三个操作中选取一个最小的值赋格当前的dp[i][j]
(三)总结:状态方程为:
if(word1[i] == word2[j]):
      dp[i][j] = dp[i-1][j-1]
else:
       min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
PS:大佬的代码中word1.charAt(i-1)==word2.charAt(j-1)的原因是:
     初始化DP Table时dp[i][0]和dp[0][j]已经填写完成,所以接下来填表需要从1开始,
     但是字符的比较需要从0开始,因此才这样子写

复杂度分析

时间复杂度：O(N^2)，这里 N 是数组的长度，我们写了两个 for 循环，每个 for 循环的时间复杂度都是线性的；

空间复杂度：O(N)，要使用和输入数组长度相等的状态数组，因此空间复杂度是 O(N)。

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离

最长重复子数组【MID】

题干

解题思路

1 定义状态（定义子问题）

2 定义状态转移方程

3 初始化状态

4 求解方向

5 找到最终解

代码实现

复杂度分析

最长公共子串【MID】

题干

解题思路

1. 状态定义

2. 状态转移方程

3. 状态的初始化

4. 遍历方向与范围

5. 最终返回结果

代码实现

复杂度分析

最长公共子序列【MID】

题干

解题思路

1. 状态定义

2. 状态转移方程

3. 状态的初始化

4. 遍历方向与范围

5. 最终返回结果

代码实现

复杂度分析

编辑距离【HARD】

题干

解题思路

暴力递归

情况一：什么都不做

情况二：插入操作

情况三：删除操作

情况四：替换操作

动态规划

代码实现

复杂度分析

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【算法训练-动态规划三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离