dp_len[0][j] = 0, dp_cnt[0][j] = 1  (空序列)
dp_len[i][0] = 0, dp_cnt[i][0] = 1

最长公共子序列的长度与个数（统计所有不同最长公共子序列的个数） 题目描述： 给定两个字符串 text1 和 text2 ，找出它们的最长公共子序列（LCS）的长度，并统计所有不同的最长公共子序列的个数。注意，只要子序列的内容（字符顺序）相同，即使来自字符串中的不同位置，也视为同一个子序列，只统计一次。你需要返回一个元组 (长度, 个数) 。 例如： 输入： text1 = "abcde", text2 = "ace" 最长公共子序列有："ace"。 返回： (3, 1) 。 输入： text1 = "abc", text2 = "abc" 最长公共子序列有："a"、"b"、"c"、"ab"、"ac"、"bc"、"abc" 共7个，但最长的只有 "abc"。 返回： (3, 1) 。 输入： text1 = "abc", text2 = "acb" 最长公共子序列有："ab" 和 "ac"，长度均为2。 返回： (2, 2) 。 解题过程循序渐进讲解： 步骤1：理解问题与基本定义 首先，回顾最长公共子序列（LCS）的定义： 子序列：从原字符串中删除一些字符（也可以不删除）后，剩余字符的相对顺序保持不变形成的新字符串。 公共子序列：同时是 text1 和 text2 的子序列的字符串。 我们需要两个结果： 长度 ：传统LCS问题，可以用动态规划计算。 个数 ：统计所有不同的最长公共子序列（即所有长度为LCS长度的公共子序列）的数量，且内容相同的子序列只算一个。 难点在于去重：例如 text1 = "aaa", text2 = "aaa" ，最长公共子序列只有 "a"、"aa"、"aaa"，但 "a" 可以由不同位置的 'a' 组成，但内容相同，因此只能算作1个。我们需要避免重复计数。 步骤2：传统LCS长度的动态规划 设 dp_len[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的LCS长度（ i 和 j 表示前缀长度）。 递推公式： 如果 text1[i-1] == text2[j-1] ，则 dp_len[i][j] = dp_len[i-1][j-1] + 1 。 否则， dp_len[i][j] = max(dp_len[i-1][j], dp_len[i][j-1]) 。 初始化： dp_len[0][j] = dp_len[i][0] = 0 。 例如： text1 = "abcde", text2 = "ace" 最终 dp_len[5][3] = 3 ，即最长长度为3。 步骤3：扩展动态规划以统计个数 我们定义另一个动态规划数组 dp_cnt[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的所有不同最长公共子序列的个数（注意：这里的“最长”指的是对于前缀 (i,j) 而言的LCS长度，不一定是全局最长）。 关键在于递推时要去重。我们考虑如下情况： 设当前比较字符 a = text1[i-1] , b = text2[j-1] 。 情况1： a == b 此时，字符 a 可以作为一个公共字符，附加到所有 dp_len[i-1][j-1] 对应的LCS后面，形成新的LCS。 因此，新的LCS长度是 dp_len[i-1][j-1] + 1 。 对于个数：所有 dp_cnt[i-1][j-1] 中的每个最长公共子序列，都可以扩展一个字符 a ，形成新的LCS。但要注意，如果之前已经有相同内容的LCS，我们需要避免重复。 关键点：当 a == b 时，当前 dp_len[i][j] 应该等于 dp_len[i-1][j-1] + 1 。那么， dp_cnt[i][j] 应该等于 dp_cnt[i-1][j-1] 吗？不一定，因为可能还有其他方式形成相同长度的LCS。 实际上，我们需要考虑三个来源的LCS： 来自 dp_len[i-1][j-1] 的每个LCS加上字符 a 形成的新LCS。 来自 dp_len[i-1][j] 的LCS（即不包含 a 但可能已经包含某些相同长度的LCS）。 来自 dp_len[i][j-1] 的LCS。 但要避免重复计数。例如，如果某个LCS既可以从 dp_len[i-1][j-1] 扩展得到，又可以从 dp_len[i-1][j] 得到，就会被重复计算。 去重策略 ： 我们定义 dp_len[i][j] 为当前前缀的LCS长度。 如果 a == b ，则 dp_len[i][j] = dp_len[i-1][j-1] + 1 。 接下来统计个数时，我们只累加那些能产生长度为 dp_len[i][j] 的LCS的来源，并且减去重复部分。 具体规则： 初始化 dp_cnt[0][j] = dp_cnt[i][0] = 1 （空子序列算一个）。 对于每个 (i, j) ： 如果 a == b ，说明可以扩展。那么所有 dp_cnt[i-1][j-1] 中的LCS都可以扩展一个字符，形成新的LCS。所以初步有 cnt = dp_cnt[i-1][j-1] 。 然后检查 dp_len[i-1][j] 和 dp_len[i][j-1] ： 如果 dp_len[i-1][j] == dp_len[i][j] ，说明有一些LCS不包含 a 但也达到了当前最大长度，这些LCS已经在 dp_cnt[i-1][j] 中被统计过，需要加上。 同理，如果 dp_len[i][j-1] == dp_len[i][j] ，则加上 dp_cnt[i][j-1] 。 但是，如果 dp_len[i-1][j-1] 也等于 dp_len[i][j] ，那么从 dp_cnt[i-1][j-1] 扩展的LCS可能已经被包含在 dp_cnt[i-1][j] 或 dp_cnt[i][j-1] 中，导致重复。具体来说，如果 dp_len[i-1][j] == dp_len[i][j] 且 dp_len[i][j-1] == dp_len[i][j] 且 dp_len[i-1][j-1] == dp_len[i][j] - 1 ，那么扩展的部分是新的，但非扩展的部分可能重复。实际上，重复发生在当 dp_len[i-1][j] 和 dp_len[i][j-1] 都达到 dp_len[i][j] 且它们共享一些相同LCS时，这些LCS来自 dp_cnt[i-1][j-1] 的非扩展版本。因此，如果 dp_len[i-1][j-1] 严格小于 dp_len[i][j] ，则不会重复；如果相等，则重复计算了 dp_cnt[i-1][j-1] 中的LCS（未扩展的）。但注意，当 a == b 时， dp_len[i-1][j-1] 不可能等于 dp_len[i][j] （因为加了1），所以不会重复。 然而，还有另一种重复：如果 dp_len[i-1][j] == dp_len[i][j] 且 dp_len[i][j-1] == dp_len[i][j] ，且它们包含相同的LCS（即来自 dp_len[i-1][j-1] 的LCS），那么这些LCS在 dp_cnt[i-1][j] 和 dp_cnt[i][j-1] 中被重复计算了。因此，如果 dp_len[i-1][j] == dp_len[i][j] 且 dp_len[i][j-1] == dp_len[i][j] ，我们需要减去 dp_cnt[i-1][j-1] 来去重（因为这部分被加了两次）。 但更常见的做法是采用以下递推： 如果 a == b ，则 dp_len[i][j] = dp_len[i-1][j-1] + 1 ，并且 dp_cnt[i][j] = dp_cnt[i-1][j-1] （因为新增的LCS都是由扩展得到的）。 然后，比较其他方向： 如果 dp_len[i-1][j] == dp_len[i][j] ，则 dp_cnt[i][j] += dp_cnt[i-1][j] 。 如果 dp_len[i][j-1] == dp_len[i][j] ，则 dp_cnt[i][j] += dp_cnt[i][j-1] 。 如果 dp_len[i-1][j] == dp_len[i][j] 且 dp_len[i][j-1] == dp_len[i][j] 且 dp_len[i-1][j-1] == dp_len[i][j] ，则说明 dp_cnt[i-1][j] 和 dp_cnt[i][j-1] 都包含了来自 dp_cnt[i-1][j-1] 的LCS，因此减去 dp_cnt[i-1][j-1] 避免重复。 如果 a != b ，则： dp_len[i][j] = max(dp_len[i-1][j], dp_len[i][j-1]) 。 初始化 dp_cnt[i][j] = 0 。 如果 dp_len[i-1][j] == dp_len[i][j] ，则 dp_cnt[i][j] += dp_cnt[i-1][j] 。 如果 dp_len[i][j-1] == dp_len[i][j] ，则 dp_cnt[i][j] += dp_cnt[i][j-1] 。 如果 dp_len[i-1][j] == dp_len[i][j] 且 dp_len[i][j-1] == dp_len[i][j] 且 dp_len[i-1][j-1] == dp_len[i][j] ，则减去 dp_cnt[i-1][j-1] 。 步骤4：举例演算 以 text1 = "abc", text2 = "acb" 为例，我们计算长度和个数。 初始化： 矩阵维度 (4,4)： i=0: text1前缀为空；j=0: text2前缀为空。 我们逐步填充： i=1, j=1: text1[ 0]='a', text2[ 0 ]='a'，相等。 dp_ len[ 1][ 1] = dp_ len[ 0][ 0 ] + 1 = 1。 dp_ cnt[ 1][ 1] = dp_ cnt[ 0][ 0 ] = 1。 检查 dp_ len[ 0][ 1]==1? 否（0）。dp_ len[ 1][ 0 ]==1? 否（0）。所以不加不减。 i=1, j=2: 'a' != 'c'。 dp_ len[ 1][ 2] = max(dp_ len[ 0][ 2]=0, dp_ len[ 1][ 1 ]=1) = 1。 dp_ cnt初始0。 dp_ len[ 0][ 2 ]==1? 否。不加。 dp_ len[ 1][ 1]==1? 是，加 dp_ cnt[ 1][ 1]=1。所以 dp_ cnt[ 1][ 2 ]=1。 dp_ len[ 0][ 2 ]==1? 否，所以不减。 i=1, j=3: 'a' != 'b'。 dp_ len[ 1][ 3] = max(dp_ len[ 0][ 3]=0, dp_ len[ 1][ 2 ]=1) = 1。 dp_ cnt=0。 dp_ len[ 0][ 3 ]==1? 否。 dp_ len[ 1][ 2]==1? 是，加 dp_ cnt[ 1][ 2]=1。所以 dp_ cnt[ 1][ 3 ]=1。 i=2, j=1: 'b' != 'a'。 dp_ len[ 2][ 1] = max(dp_ len[ 1][ 1]=1, dp_ len[ 2][ 0 ]=0) = 1。 dp_ cnt=0。 dp_ len[ 1][ 1]==1? 是，加 dp_ cnt[ 1][ 1]=1。所以 dp_ cnt[ 2][ 1 ]=1。 i=2, j=2: 'b' != 'c'。 dp_ len[ 2][ 2] = max(dp_ len[ 1][ 2]=1, dp_ len[ 2][ 1 ]=1) = 1。 dp_ cnt=0。 dp_ len[ 1][ 2 ]==1? 是，加1。 dp_ len[ 2][ 1 ]==1? 是，加1。 现在 dp_ cnt=2。 检查 dp_ len[ 1][ 1]==1? 是，且 dp_ len[ 1][ 2]==1 和 dp_ len[ 2][ 1]==1 都满足，所以减去 dp_ cnt[ 1][ 1 ]=1。 最终 dp_ cnt[ 2][ 2 ] = 1。 i=2, j=3: 'b' == 'b'。 dp_ len[ 2][ 3] = dp_ len[ 1][ 2 ] + 1 = 1+1=2。 dp_ cnt[ 2][ 3] = dp_ cnt[ 1][ 2 ] = 1。 检查 dp_ len[ 1][ 3 ]==2? 否（1）。 dp_ len[ 2][ 2 ]==2? 否（1）。 所以不加不减。 i=3, j=1: 'c' != 'a'。 dp_ len[ 3][ 1] = max(dp_ len[ 2][ 1]=1, dp_ len[ 3][ 0 ]=0) = 1。 dp_ cnt=0。 dp_ len[ 2][ 1 ]==1? 是，加1。 所以 dp_ cnt[ 3][ 1 ]=1。 i=3, j=2: 'c' == 'c'。 dp_ len[ 3][ 2] = dp_ len[ 2][ 1 ] + 1 = 1+1=2。 dp_ cnt[ 3][ 2] = dp_ cnt[ 2][ 1 ] = 1。 检查 dp_ len[ 2][ 2 ]==2? 否（1）。 dp_ len[ 3][ 1 ]==2? 否（1）。 所以不加。 i=3, j=3: 'c' != 'b'。 dp_ len[ 3][ 3] = max(dp_ len[ 2][ 3]=2, dp_ len[ 3][ 2 ]=2) = 2。 dp_ cnt=0。 dp_ len[ 2][ 3]==2? 是，加 dp_ cnt[ 2][ 3 ]=1。 dp_ len[ 3][ 2]==2? 是，加 dp_ cnt[ 3][ 2 ]=1。 现在 dp_ cnt=2。 检查 dp_ len[ 2][ 2 ]==2? 否（1），所以不减。 最终 dp_ cnt[ 3][ 3 ] = 2。 所以最长长度为 dp_ len[ 3][ 3] = 2，个数为 dp_ cnt[ 3][ 3 ] = 2。 符合例子：最长公共子序列有 "ab" 和 "ac"。 步骤5：算法总结 定义 dp_len[i][j] 和 dp_cnt[i][j] ，大小均为 (n+1) x (m+1) ，初始 dp_len[0][j]=dp_len[i][0]=0 ， dp_cnt[0][j]=dp_cnt[i][0]=1 （空序列计数为1）。 遍历 i=1..n, j=1..m： 如果 text1[i-1] == text2[j-1] ： dp_len[i][j] = dp_len[i-1][j-1] + 1 dp_cnt[i][j] = dp_cnt[i-1][j-1] 否则： dp_len[i][j] = max(dp_len[i-1][j], dp_len[i][j-1]) dp_cnt[i][j] = 0 然后，对于 a == b 和 a != b 两种情况，都需要处理额外累加： 如果 dp_len[i-1][j] == dp_len[i][j] ，则 dp_cnt[i][j] += dp_cnt[i-1][j] 如果 dp_len[i][j-1] == dp_len[i][j] ，则 dp_cnt[i][j] += dp_cnt[i][j-1] 如果 dp_len[i-1][j] == dp_len[i][j] 且 dp_len[i][j-1] == dp_len[i][j] 且 dp_len[i-1][j-1] == dp_len[i][j] ，则 dp_cnt[i][j] -= dp_cnt[i-1][j-1] 最终结果： dp_len[n][m] 为长度， dp_cnt[n][m] 为个数。 注意：由于数字可能很大，通常需要对结果取模（如 10^9+7），但本题只要求统计个数，假设在整数范围内。 步骤6：复杂度分析 时间复杂度：O(n* m)，需要填充两个二维表格。 空间复杂度：O(n* m)，可优化到 O(min(n,m)) 但实现稍复杂。 这个算法巧妙地结合了长度和个数的计算，通过比较相邻状态的长度值来累加个数并去重，确保了每个不同的最长公共子序列只被计数一次。