最长公共子序列
简介
最长公共子序列（Longest Common Subsequence），英文缩写为LCS。其定义是，一个序列 S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
应用
应用1：Leetcode.1143
题目
解题思路
动态规划
设 \(dp[i][j]\) 表示字符串 \(text_1\) 的前 \(i\) 个字符，与字符串 \(text_2\) 的前 \(j\) 个字符的最长公共子序列。
即子串 \(text_1[:i-1]\) 与 \(text_2[:j-1]\) 的最长公共子序列的长度，注意，数组序号是从 \(0\) 开始的，\(i-1\) 表示前 \(i\) 个字符，那么：
初始状态
当其中一个字符串的长度为 \(0\) 时，没有公共子序列，所以，任意一个字符长度为 \(0\) 时，最长公共子序列的长度为 \(0\) ，即：
\[\begin{align} dp[0][j] = 0 \\ dp[i][0] = 0 \end{align} \]状态转移
我们分别枚举两个字符串，会出现两种情况：
- 如果当前两个字符相等，那么当前状态 \(dp[i][j]\) 就可以由上一个状态 \(dp[i - 1][j - 1]\) 加 \(1\) ；
- 如果当前两个字符不相等，那么当前状态 \(dp[i][j]\) 就要从 \(dp[i][j - 1]\) 或者 \(dp[i - 1][j]\) 中取最大值。
所以，状态转移方程如下：
\[dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1, & text_1[i] = text_2[j] \\ max(dp[i][j - 1],\ dp[i - 1][j]), & text_1[i] \neq text_2[j] \\ \end{cases} \]代码实现
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
# 如果当前两个字符串中的字符相等，则直接移动两个字符串的指针
if text1[i -1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[m][n]