动态规划法求最长公共子序列，要求自己输入元素

好的，下面我将介绍使用动态规划法求解最长公共子序列问题。

首先，让我们了解一下什么是最长公共子序列。最长公共子序列（LCS）是指两个或多个字符串中，所有顺序相同且长度最长的子序列。

接下来，我们按照以下步骤使用动态规划求解LCS问题：

1. 定义状态：设字符串A和B的长度分别为m和n，则定义一个m+1行、n+1列的二维数组dp，其中dp[i][j]表示A的前i个字符和B的前j个字符的LCS长度。

2. 初始化：将dp数组第一行和第一列的元素全部置为0，因为任意一个字符串与空字符串的LCS长度均为0。

3. 状态转移方程：当A[i]等于B[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]即为A和B的LCS长度。

5. 逆推求解LCS：从dp[m][n]开始，根据状态转移方程逆推得到LCS。

下面是Python代码实现：

def lcs(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n+1) for _ in range(m+1)]
    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])
    length = dp[m][n]
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if A[i-1] == B[j-1]:
            result.append(A[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    result.reverse()
    return length, ''.join(result)

其中，A和B分别为输入的字符串，返回值为LCS长度和LCS本身。