2.动态规划法求解最长公共子序列问题的算法伪代码描述

算法描述：

设有两个序列A和B，长度分别为m和n，求它们的最长公共子序列。

动态规划法的基本思路是：用一个二维数组dp[m+1][n+1]表示A和B的任意子序列的LCS长度，其中dp[i][j]表示A[1..i]和B[1..j]的LCS长度。则可以得到状态转移方程：

当 A[i] == B[j] 时：dp[i][j] = dp[i-1][j-1] + 1;

当 A[i] != B[j] 时：dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

最终的LCS长度即为dp[m][n]。

伪代码描述：

func longestCommonSubsequence(A[1..m], B[1..n])
// 初始化二维数组
dp[0..m][0..n] = 0

for i = 1 to m
for j = 1 to n
if A[i] == B[j]
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]