好的，我为你随机挑选一个尚未讲过的线性动态规划题目。

最长公共子序列的变种：最长公共子序列的长度与具体序列（输出一个具体的最长公共子序列）

题目描述

给定两个字符串 text1 和 text2，要求：

1. 找出它们的最长公共子序列（LCS）的长度。
2. 输出任意一个最长公共子序列的具体内容（如果 LCS 长度大于 0）。

示例 1
输入：
text1 = "abcde"
text2 = "ace"
输出：
长度 = 3
一个 LCS = "ace"

示例 2
输入：
text1 = "abc"
text2 = "abc"
输出：
长度 = 3
一个 LCS = "abc"

示例 3
输入：
text1 = "abc"
text2 = "def"
输出：
长度 = 0
一个 LCS = ""

解题过程循序渐进讲解

第一步：理解最长公共子序列（LCS）

最长公共子序列的定义是：在两个字符串中按原顺序出现（不一定连续）的最长子序列。
例如 "abcde" 与 "ace" 的 LCS 可以是 "ace"、"acd" 等，长度都是 3。

第二步：先用动态规划求长度

我们定义 dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的 LCS 长度。
初始化：dp[0][j] = 0, dp[i][0] = 0，因为空串与任何字符串的 LCS 长度为 0。

状态转移：

• 如果 text1[i-1] == text2[j-1]，说明当前字符可以加入 LCS：
  dp[i][j] = dp[i-1][j-1] + 1
• 如果不相等，则 LCS 只能来自两个方向之一：
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

递推完成后，dp[m][n] 就是最长公共子序列的长度。

例子：text1 = "abcde", text2 = "ace"
我们填一个简化的表格（只给关键值）：
dp[5][3] 的求法：

   a c e
 a 1 1 1
 b 1 1 1
 c 1 2 2
 d 1 2 2
 e 1 2 3

最后 dp[5][3] = 3。

第三步：根据 dp 表格回溯构造一个 LCS

我们知道 dp[m][n] 是长度，但具体是哪些字符呢？
我们从 (m, n) 往 (0, 0) 回溯：

• 如果 text1[i-1] == text2[j-1]，说明这个字符是 LCS 的一部分，加入结果，然后移到 (i-1, j-1)。
• 否则，看 dp[i-1][j] 和 dp[i][j-1] 哪个等于 dp[i][j]，往大的方向走（如果相等，任选一个方向，会得到不同的 LCS 之一）。

继续以上面的例子演示：

1. i=5, j=3，text1[4]='e', text2[2]='e'，相等 → 加入 'e'，去 (4,2)。
2. i=4, j=2，text1[3]='d', text2[1]='c'，不等，比较 dp[3][2]=2 与 dp[4][1]=1，取大的 (3,2)（即向上走）。
3. i=3, j=2，text1[2]='c', text2[1]='c'，相等 → 加入 'c'，去 (2,1)。
4. i=2, j=1，text1[1]='b', text2[0]='a'，不等，比较 dp[1][1]=1 与 dp[2][0]=0，取大的 (1,1)。
5. i=1, j=1，text1[0]='a', text2[0]='a'，相等 → 加入 'a'，去 (0,0)。
6. 结束。

收集的顺序是反向的：'e'、'c'、'a'，反转后得到 "ace"。

第四步：伪代码描述

函数 LCS(text1, text2):
    m = text1长度, n = text2长度
    创建 dp[m+1][n+1] 并初始化为 0
    for i from 1 to m:
        for j from 1 to n:
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 回溯找序列
    result = []
    i = m, j = n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i--, j--
        else if dp[i-1][j] > dp[i][j-1]:
            i--
        else:
            j--
    反转 result 得到正序 LCS
    返回 dp[m][n] 和 result

第五步：时间复杂度与空间复杂度

• 求长度：O(m*n)
• 回溯构造：O(m+n)
• 总时间复杂度：O(m*n)
• 空间复杂度：O(mn)（可以优化到 O(min(m,n)) 如果只求长度，但构造序列通常需要 O(mn) 来存储 dp 以便回溯）

第六步：讨论构造多个 LCS

如果题目要求输出所有 LCS，我们需要在回溯时遇到 dp[i-1][j] == dp[i][j-1] 且不等于 dp[i][j] 时，两个分支都走，用 DFS 收集所有可能。但本题只要求输出一个即可，所以按上面的方法即可。