最长公共子序列算法思想

最长公共子序列（LCS）算法的思想是动态规划。具体来说，我们可以定义两个序列X和Y，它们的长度分别为m和n。我们用c[i][j]来表示X的前i个字符和Y的前j个字符的LCS长度。那么，c[m][n]就是X和Y的LCS长度。

接下来，我们考虑如何计算c[i][j]。如果X的最后一个字符和Y的最后一个字符相同，那么它们一定在LCS中。因此，LCS的长度就是X的前i-1个字符和Y的前j-1个字符的LCS长度加1，即c[i][j] = c[i-1][j-1] + 1。如果X的最后一个字符和Y的最后一个字符不同，那么它们不能同时出现在LCS中。因此，LCS的长度就是X的前i个字符和Y的前j-1个字符的LCS长度和X的前i-1个字符和Y的前j个字符的LCS长度的最大值，即c[i][j] = max(c[i][j-1], c[i-1][j])。

最后，我们可以使用递推的方式计算c[i][j]，最终得到c[m][n]。同时，我们可以使用回溯的方式，构造出LCS本身。