求最长公共子序列的算法思想

最长公共子序列（Longest Common Subsequence，LCS）是指在两个序列中，找到一个最长的公共子序列，并且该子序列在两个序列中的位置顺序都一致。比如序列 A={A,B,C,B,D,A,B} 和序列 B={B,D,C,A,B,A} 的最长公共子序列为 {B,C,A,B}。

求最长公共子序列的算法思想主要有动态规划和回溯两种方法。

动态规划方法的基本思想是，使用一个二维数组 dp[i][j] 来存储序列 A 的前 i 个元素和序列 B 的前 j 个元素的最长公共子序列长度，然后逐个计算 dp[i][j] 的值。具体地，如果 A[i-1] 等于 B[j-1]，那么 dp[i][j] 就等于 dp[i-1][j-1] 加上 1；否则，dp[i][j] 就等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值。最后，dp[m][n] 就是序列 A 和 B 的最长公共子序列长度，其中 m 和 n 分别是序列 A 和 B 的长度。

回溯方法的基本思想是，先使用动态规划方法求得最长公共子序列长度，然后从 dp[m][n] 开始，逆向回溯得到最长公共子序列。具体地，从 dp[m][n] 开始，如果 A[m-1] 等于 B[n-1]，那么这个字符就是最长公共子序列的一个字符，然后向左上方移动一个位置继续寻找；否则，向 dp[i-1][j] 和 dp[i][j-1] 中值较大的位置移动。重复此过程直到回溯到 dp[0][0]。