用动态规划解决最长公共子序列问题，要求给出问题描述及算法设计思路，用伪代码描述算法，最后分析算法的复杂度

问题描述：给定两个序列 X 和 Y，求它们的最长公共子序列。

算法设计思路：动态规划

1. 状态定义：dp[i][j] 表示序列 X 的前 i 个元素和序列 Y 的前 j 个元素的最长公共子序列长度。

2. 初始状态：dp[0][j] = 0，dp[i][0] = 0。

3. 状态转移方程：当 X[i] = Y[j] 时，dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

4. 最终结果：dp[m][n]，其中 m 和 n 分别为序列 X 和 Y 的长度。

伪代码描述：

function longest_common_subsequence(X, Y):
    m = length(X)
    n = length(Y)
    dp = new array(m+1, n+1)
    for i from 0 to m:
        dp[i][0] = 0
    for j from 0 to n:
        dp[0][j] = 0
    for i from 1 to m:
        for j from 1 to n:
            if X[i] == Y[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]

算法复杂度分析：时间复杂度为 O(mn)，空间复杂度为 O(mn)，其中 m 和 n 分别为序列 X 和 Y 的长度。