动态规划——最长公共子序列

动态规划相关知识

求解最长的公共子序列

问题定义与区分：理解最长公共子串与最长公共子序列的区别。
动态规划思想：利用二维数组 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[i][j] ) 表示：
字符串 ( S_1 ) 的前 ( i ) 个字符 和 字符串 ( S_2 ) 的前 ( j ) 个字符 的最长公共子序列长度。

当 ( S_1[i] = S_2[j] )：
两个字符相等时，最长公共子序列长度为：
[
dp[i][j] = dp[i-1][j-1] + 1
]
当 ( S_1[i] \neq S_2[j] )：
两个字符不相等时，最长公共子序列长度取左边和上边的最大值：
[
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
]
初始化：
- ( dp[0][j] = 0 )：与空字符串匹配的最长公共子序列长度为 0。
- ( dp[i][0] = 0 )：与空字符串匹配的最长公共子序列长度为 0。

初始化：
- 第 0 行和第 0 列初始化为 0。
填充规则：
- 若 ( 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]) )
示例填充：
- 第 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 )。