最长公共子序列的伪代码

以下是最长公共子序列（Longest Common Subsequence，LCS）的伪代码：

输入：字符串A和字符串B，长度分别为m和n
输出：最长公共子序列的长度和该子序列

1. 初始化一个(m+1) * (n+1)的矩阵dp，全部赋值为0
2. for i in range(1, m+1):
for j in range(1, n+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. lcs_len = dp[m][n]
4. 初始化一个空序列lcs
5. while lcs_len > 0:
if A[m-1] == B[n-1]:
lcs.append(A[m-1])
m -= 1
n -= 1
lcs_len -= 1
elif dp[m-1][n] >= dp[m][n-1]:
m -= 1
else:
n -= 1
6. 将lcs序列反转，得到最长公共子序列

解释：首先，创建一个二维的dp数组，用来存储最长公共子序列的长度。然后，我们遍历字符串A和B中的所有字符，如果字符相同，则在dp[i][j]中存储dp[i-1][j-1]+1，表示当前字符在最长公共子序列中。如果字符不同，则在dp[i][j]中存储max(dp[i-1][j], dp[i][j-1])，表示当前字符不在最长公共子序列中，需要在A前缀和B前缀的子序列中寻找最长公共子序列。最终，我们可以通过回溯dp数组，构造出最长公共子序列。