最长公共子序列 (Longest Common Subsequence) 的变种：统计所有不同的最长公共子序列的个数 题目描述 给定两个字符串 s 和 t ，请你计算它们的 最长公共子序列 (Longest Common Subsequence, LCS) 的长度，并进一步统计 所有不同的最长公共子序列 (distinct LCS) 的个数。注意，这里的“不同”是指不同的字符串，即使它们来自原字符串的不同位置，只要内容相同就视为同一个。 例如： 输入： s = "abc", t = "abc" LCS 长度为 3，不同的 LCS 个数为 1（只有 "abc" ）。 输入： s = "ab", t = "ab" LCS 长度为 2，不同的 LCS 个数为 1（只有 "ab" ）。 输入： s = "aab", t = "aba" LCS 可以是 "ab" 或 "aa" ，长度为 2，不同的 LCS 个数为 2（ "ab" 和 "aa" ）。 题目要求： 计算 LCS 的长度，并统计所有不同的最长公共子序列的个数。由于结果可能很大，答案需要对一个质数（如 10^9 + 7）取模。 解题思路 这是经典 LCS 问题的扩展。经典 LCS 只求长度，而这里还需要统计不同的最长公共子序列的个数。我们需要在动态规划的基础上，额外维护一个计数数组来记录不同的 LCS 个数。 步骤 1：定义状态 设 s 的长度为 n ， t 的长度为 m 。 定义 dp[i][j] 表示 s 的前 i 个字符（下标 1 到 i）和 t 的前 j 个字符（下标 1 到 j）的 LCS 长度。 定义 cnt[i][j] 表示在 s 的前 i 个字符和 t 的前 j 个字符中，长度为 dp[i][j] 的不同公共子序列的个数。 步骤 2：状态转移 考虑 s[i] 和 t[j] 的关系： 如果 s[i] == t[j] ： 说明当前字符可以加入 LCS 中。 长度转移： dp[i][j] = dp[i-1][j-1] + 1 个数转移： cnt[i][j] = cnt[i-1][j-1] （因为当前字符唯一确定了新的公共子序列，所以个数等于之前的个数） 这里需要特别注意：如果存在其他情况也能得到相同长度的 LCS，我们需要把这些情况也加进来。但在这个基本问题中，当字符相等时，新增的公共子序列是唯一的，所以个数直接继承。 如果 s[i] != t[j] ： 我们无法同时使用 s[i] 和 t[j] ，只能从 (i-1, j) 和 (i, j-1) 转移。 先比较 dp[i-1][j] 和 dp[i][j-1] 的大小： 如果 dp[i-1][j] > dp[i][j-1] ，则 dp[i][j] = dp[i-1][j] ，且 cnt[i][j] = cnt[i-1][j] 。 如果 dp[i-1][j] < dp[i][j-1] ，则 dp[i][j] = dp[i][j-1] ，且 cnt[i][j] = cnt[i][j-1] 。 如果 dp[i-1][j] == dp[i][j-1] ，则 dp[i][j] = dp[i-1][j] ，但此时 cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] ，因为两种转移都能得到相同长度的 LCS，并且它们的公共子序列集合可能有重叠，但我们需要去掉重复的。 注意重叠的部分是 cnt[i-1][j-1] （当 dp[i-1][j-1] 也等于这个长度时），因为如果 dp[i-1][j] 和 dp[i][j-1] 的 LCS 都来自 dp[i-1][j-1] ，那么会被重复计算。所以我们需要在 dp[i-1][j] == dp[i][j-1] 的情况下，如果 dp[i-1][j-1] 也等于这个长度，则减去 cnt[i-1][j-1] 以避免重复。 步骤 3：初始化 dp[0][j] = 0 和 dp[i][0] = 0 表示空串的 LCS 长度为 0。 cnt[0][j] = 1 和 cnt[i][0] = 1 表示空串的个数为 1（空串本身）。 这是为了在转移时，当字符相等时， cnt[i][j] 可以从 cnt[i-1][j-1] 继承，而 cnt[0][0] = 1 是合理的。 步骤 4：计算顺序 从 i = 1 到 n ， j = 1 到 m 顺序计算。 步骤 5：结果 LCS 长度为 dp[n][m] 。 不同的 LCS 个数为 cnt[n][m] 。 举例说明 以 s = "aab", t = "aba" 为例： 构建 dp 和 cnt 表（下标从 1 开始）： 初始化： dp[0][:] = 0, dp[:][0] = 0 ； cnt[0][:] = 1, cnt[:][0] = 1 。 逐步计算： i=1, j=1 : s[ 1]='a', t[ 1]='a'，相等， dp[1][1]=1 , cnt[1][1]=cnt[0][0]=1 。 i=1, j=2 : s[ 1]='a', t[ 2]='b'，不等， dp[0][2]=0, dp[1][1]=1 ，取最大长度 1， cnt[1][2]=cnt[1][1]=1 。 i=1, j=3 : s[ 1]='a', t[ 3]='a'，相等， dp[1][3]=dp[0][2]+1=1 , cnt[1][3]=cnt[0][2]=1 。 i=2, j=1 : s[ 2]='a', t[ 1]='a'，相等， dp[2][1]=dp[1][0]+1=1 , cnt[2][1]=cnt[1][0]=1 。 i=2, j=2 : s[ 2]='a', t[ 2]='b'，不等， dp[1][2]=1, dp[2][1]=1 ，相等，所以 dp[2][2]=1 ， cnt[2][2]=cnt[1][2]+cnt[2][1]-cnt[1][1]=1+1-1=1 。 i=2, j=3 : s[ 2]='a', t[ 3]='a'，相等， dp[2][3]=dp[1][2]+1=2 , cnt[2][3]=cnt[1][2]=1 。 i=3, j=1 : s[ 3]='b', t[ 1]='a'，不等， dp[2][1]=1, dp[3][0]=0 ，取最大 1， cnt[3][1]=cnt[2][1]=1 。 i=3, j=2 : s[ 3]='b', t[ 2]='b'，相等， dp[3][2]=dp[2][1]+1=2 , cnt[3][2]=cnt[2][1]=1 。 i=3, j=3 : s[ 3]='b', t[ 3]='a'，不等， dp[2][3]=2, dp[3][2]=2 ，相等，所以 dp[3][3]=2 ， cnt[3][3]=cnt[2][3]+cnt[3][2]-cnt[2][2]=1+1-1=1 。 注意：这里 dp[3][3] 长度是 2，但我们需要检查所有长度 2 的 LCS。实际上，从 dp[2][3] 和 dp[3][2] 都可以得到长度 2 的 LCS，它们分别是 "aa" 和 "ab" ，但这里计算个数时，因为 dp[2][2] 长度为 1，不影响。 最终结果：长度 2，个数 2。 但我们的计算中 cnt[3][3]=1 是错误的，因为上面的计算没有考虑不同 LCS 的合并。实际上，我们需要在 s[i] != t[j] 且 dp[i-1][j] == dp[i][j-1] 时，如果 dp[i-1][j-1] 小于这个长度，才直接相加；如果 dp[i-1][j-1] 等于这个长度，则需要减去重复部分。在这个例子中，我们需要在计算 cnt[3][3] 时，检查 dp[2][2] 是否等于 2，这里 dp[2][2]=1 ，所以不减。但为什么结果还是 1？ 因为我们的 cnt 定义是“长度为 dp[i][j] 的不同公共子序列个数”，但在 s[i] != t[j] 时，如果 dp[i-1][j] 和 dp[i][j-1] 的长度相等，但它们的 LCS 集合可能有重叠，我们需要合并。 实际上，更精确的方法是： 当 s[i] != t[j] 时， 如果 dp[i-1][j] > dp[i][j-1] ，则 cnt[i][j] = cnt[i-1][j] 。 如果 dp[i-1][j] < dp[i][j-1] ，则 cnt[i][j] = cnt[i][j-1] 。 如果 dp[i-1][j] == dp[i][j-1] ，则 cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] ，但如果 dp[i-1][j-1] 也等于这个长度，说明 cnt[i-1][j-1] 被重复计算了，所以要减去。 但这里 dp[2][2]=1 ，不等于 2，所以不减。 那为什么 cnt[3][3] 是 1 而不是 2？ 因为在计算 cnt[2][3] 和 cnt[3][2] 时，它们各自是 1，但它们的 LCS 集合不同（ "aa" 和 "ab" ），所以相加得 2。但我们的计算中， cnt[2][3]=1 和 cnt[3][2]=1 分别表示长度为 2 的 LCS 个数，相加是 2，并没有重复，所以 cnt[3][3] 应该是 2。 我前面的计算有误，重新计算一下： cnt[2][3] 对应 LCS "aa" ，个数 1。 cnt[3][2] 对应 LCS "ab" ，个数 1。 所以 cnt[3][3] = 1 + 1 = 2 。 最终结果：长度 2，个数 2，正确。 算法实现细节 初始化 dp 和 cnt 为二维数组，大小为 (n+1) x (m+1) 。 遍历计算，注意取模。 最终答案为 cnt[n][m] 。 复杂度分析 时间复杂度：O(n* m)。 空间复杂度：O(n* m)，可优化到 O(m)。 核心难点 在 s[i] != t[j] 且 dp[i-1][j] == dp[i][j-1] 时，需要判断 dp[i-1][j-1] 是否等于这个长度，如果是，则需要减去 cnt[i-1][j-1] 以避免重复计数。这是因为如果 dp[i-1][j] 和 dp[i][j-1] 的 LCS 都来自 dp[i-1][j-1] 的扩展，那么这些 LCS 会被重复计算两次。 这个题目结合了 LCS 长度计算和不同序列的计数，是线性动态规划中一个经典的变种问题。