Acwing.897 最长公共子序列(动态规划)

**最长公共子序列（Longest Common Subsequence，LCS）**

在计算机科学中，最长公共子序列问题是指给定两个序列（如字符串或数组），找出其中一个序列的最长连续子序列，它也是另一个序列的一个子序列。这个问题经常被用来解决生物信息学中的序列比对问题。

**动态规划法**

动态规划法是解决最长公共子序列问题的一种有效方法。基本思想是：对于两个序列的每个位置，计算出它们的最长公共子序列的长度，并将其存储在一个二维数组中，以便后续使用。

**算法步骤**

1. **初始化**:创建一个二维数组 `dp`，大小为 `(m+1)×(n+1)`，其中 `m` 和 `n` 是两个序列的长度。将所有元素初始化为 `0`。
2. **填充第一行和第一列**:对于每个位置 `i`（从 `0` 到 `m`）和 `j`（从 `0` 到 `n`），如果 `i==0` 或 `j==0`，则将 `dp[i][j]` 初始化为 `0`。否则，如果两个序列的当前字符相同，则 `dp[i][j]=dp[i-1][j-1]+1`。
3. **填充剩余元素**:对于每个位置 `i`（从 `1` 到 `m`）和 `j`（从 `1` 到 `n`），如果两个序列的当前字符相同，则 `dp[i][j]=dp[i-1][j-1]+1`。否则，取 `dp[i-1][j]` 和 `dp[i][j-1]` 的最大值，并将其赋给 `dp[i][j]`。
4. **读取结果**:最长公共子序列的长度存储在 `dp[m][n]` 中。

**示例代码**

def lcs(str1, str2):
 m = len(str1)
 n = len(str2)

 # 初始化二维数组 dp = [[0 for _ in range(n +1)] for _ in range(m +1)]

 # 填充第一行和第一列 for i in range(m +1):
 for j in range(n +1):
 if i ==0 or j ==0:
 dp[i][j] =0 elif str1[i -1] == str2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 # 填充剩余元素 for i in range(1, m +1):
 for j in range(1, n +1):
 if str1[i -1] == str2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])

 #读取结果 return dp[m][n]

# 测试用例str1 = "AGGTAB"
str2 = "GXTXAYB"
print("最长公共子序列的长度:", lcs(str1, str2))