概要

动态规划相关知识

求解最长的公共子序列

整体流程

问题定义与区分：理解最长公共子串与最长公共子序列的区别。
动态规划思想：利用二维数组 dp 保存子问题结果，逐步推导递推公式。
递推公式推导：通过分析不同情况下的子序列关系，得出 dp 的状态转移方程。
结果总结：从表格中找到最长公共子序列的长度及具体子序列。

问题描述

理清背景

可能看上面的图片会晦涩难懂些，接下来用实例解释

我们可以给出两个序列S1和S2

若是求解公共子串，那么最大的公共子串就是ABC
而求解最大公共子序列，便是EABCE

到这里也可以看出它们之间的区别了，公共子串要求连续，而公共子串可以不连续

当序列长度较短时，我们可以通过肉眼观察得出结果。
但面对大规模数据时，仅靠人力显然不现实。因此，我们引入 动态规划 来解决这一问题。

动态规划需要的一般是：1.表格 2. 递推公式

现在需要先得到递推公式

递推公式由来

先定义二位数组dp进行保存，dp[i][j]的含义如下图，其值为最大公共子序列的长度

那么这个dp[i][j]咋球呢？分为以下三种情况

两个序列的最后一位相等

如图，最后一位都为A，那么A前的子序列的最大公共子序列则为dp[i-1][j-1]
这样放眼到完整子序列中，长度便是dp[i-1][j-1]+1

这样便可以得到递推公式

dp[i][j] = dp[i-1][j-1] + 1

两个序列的最后一位不等

左图

dp[i][j-1] 

右图

dp[i-1][j] 

假设dp[i][j-1] 的值为5，dp[i-1][j] 的值为6，求解公共子序列是不用考虑连续的，那么取两者中的最大值即可

dp[i][j] = MAX(dp[i-1][j] ，dp[i][j-1] )

得到总的递推公式

表格填写

有了递推公式后，我们便可以开始着手填写表格

dp 表格定义

我们使用动态规划 ( dp[i][j] ) 表示：
字符串 ( S_1 ) 的前 ( i ) 个字符 和 字符串 ( S_2 ) 的前 ( j ) 个字符 的最长公共子序列长度。

---

递推公式

1. 当 ( S_1[i] = S_2[j] )：
   两个字符相等时，最长公共子序列长度为：
   [
   dp[i][j] = dp[i-1][j-1] + 1
   ]

2. 当 ( S_1[i] != S_2[j] )：
   两个字符不相等时，最长公共子序列长度取左边和上边的最大值：
   [
   dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   ]

3. 初始化：

   • ( dp[0][j] = 0 )：与空字符串匹配的最长公共子序列长度为 0。
   • ( dp[i][0] = 0 )：与空字符串匹配的最长公共子序列长度为 0。

---

填表过程

	0	b	d	c	a	b	a
0	0	0	0	0	0	0	0
a	0	0	0	0	1	1	1
b	0	1	1	1	1	2	2
c	0	1	1	2	2	2	2
b	0	1	1	2	2	3	3
d	0	1	2	2	2	3	3
a	0	1	2	2	3	3	4

---

填表过程解析

1. 初始化：

   • 第 0 行和第 0 列初始化为 0。

2. 填充规则：

   • 若 ( S_1[i] = S_2[j] )：
     ( dp[i][j] = dp[i-1][j-1] + 1 )
   • 若 ( S_1[i] != S_2[j] )：
     ( dp[i][j] = max(dp[i-1][j], dp[i][j-1]) )

3. 示例填充：

   • 第 1 行：当 ( S_1[1] = a )，( S_2[4] = a )，则 ( dp[1][4] = 1 )。
   • 第 2 行：当 ( S_1[2] = b )，( S_2[1] = b )，则 ( dp[2][1] = 1 )。
   • 第 6 行：当 ( S_1[6] = a )，( S_2[6] = a )，则 ( dp[6][6] = 4 )。

---

最终结果

• 最长公共子序列长度：( dp[6][6] = 4 )。
• 最长公共子序列：通过回溯得到 “bdca”。

---

---

图示回顾：

---

通过动态规划高效解决 最长公共子序列 问题，适用于序列匹配、文本编辑等实际场景。

小结

以上笔记图来源于b站视频：包教包会～最长公共子序列