最长公共子序列的变种：限制最长公共子序列中不能出现某些禁止字符（进阶版：禁止字符可以连续出现但有限制） 题目描述 给定两个字符串 s 和 t ，以及一个禁止字符集合（或禁止模式）。我们需要找出 s 和 t 的最长公共子序列（LCS），但这个最长公共子序列必须满足： 子序列中不能包含任何禁止字符 。 更具体地，禁止规则是： 如果禁止字符集合是单个字符，那么子序列中不能出现这些字符。 进阶版：某些禁止字符（或子串模式）可以连续出现，但连续出现的次数不能超过一个上限值 K（K ≥ 0）。 注意：这里的禁止条件是针对最终得到的公共子序列的，而不是针对原始字符串的匹配过程。 示例 假设 s = "abcde", t = "ace", 禁止字符集合 = {'c'}，那么最长公共子序列不能包含字符 'c'，原本的 LCS 是 "ace" 或 "acd" 等，去掉 'c' 后，可能的 LCS 变成 "ae" 或 "ad" 等，最长长度为 2。 进阶示例：s = "aabcc", t = "aacbc", 禁止字符集合 = {'c'}，且 K=1（即最多允许连续出现 1 个 'c'）。 如果不考虑禁止，LCS 可以是 "aabc"（长度为 4，含有两个 'c' 但它们是分开的，没有连续出现）。 如果禁止 'c' 完全，则 LCS 为 "aab"（长度 3）。 如果允许最多连续 1 个 'c'，那么 "aabc" 是合法的（因为其中的 'c' 并没有连续出现），所以最长长度是 4。 解题步骤 步骤1：传统 LCS 动态规划回顾 我们先回顾经典 LCS 的 DP 定义： 定义 dp[i][j] 表示 s[ 0..i-1] 和 t[ 0..j-1 ] 的最长公共子序列长度。 递推关系： 如果 s[ i-1] == t[ j-1]，则 dp[i][j] = dp[i-1][j-1] + 1 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 步骤2：加入禁止条件的思路 禁止条件是针对构造出的公共子序列的内容，而不是针对匹配过程的。 我们需要在状态中增加一个维度，来记录当前子序列末尾连续禁止字符的数量（如果当前末尾字符是禁止字符的话），以便检查是否超过了 K 的限制。 但这里有一个问题：禁止字符是禁止“出现在子序列中”还是禁止“连续出现次数超过 K”？题目要求是“不能包含任何禁止字符”（基本版），进阶版是禁止字符可以出现，但不能连续出现超过 K 个。 我们按照进阶版来做，因为基本版是进阶版在 K=0 时的特例。 步骤3：重新定义状态 设禁止字符集合为 forbidden_ chars，K 是允许的连续出现上限。 定义 dp[i][j][cnt] 表示考虑 s 的前 i 个字符、t 的前 j 个字符，当前 LCS 的 最后一个字符 如果是禁止字符，则它连续出现了 cnt 次（cnt 从 0 到 K）；如果最后一个字符不是禁止字符，则 cnt=0 表示这种情况。 注意：cnt 的含义是“当前 LCS 末尾连续禁止字符的个数”，如果最后一个字符不是禁止字符，则 cnt=0。 但这样 cnt 的范围是 0..K，其中 cnt=0 表示末尾字符非禁止字符，cnt>=1 表示末尾是禁止字符且连续出现了 cnt 个。 状态转移 ： 我们需要考虑在匹配 s[ i-1] 和 t[ j-1 ] 时，如果它们相等，我们可以选择将其加入 LCS 末尾，那么新的 cnt 值取决于这个字符 ch 是否是禁止字符。 设 ch = s[ i-1] = t[ j-1 ]。 如果 ch 不是禁止字符，则选择它加入 LCS 时，新的末尾连续禁止字符数为 0。 如果 ch 是禁止字符，则选择它加入 LCS 时，新的末尾连续禁止字符数 = 上一个状态的 cnt' + 1，但前提是 cnt' + 1 <= K。 但上一个状态对应的 cnt' 是什么？我们需要从上一个 LCS 状态知道它的末尾连续禁止字符数。 因此，dp 状态需要记录：匹配到 s 的前 i 个、t 的前 j 个，且 LCS 末尾连续禁止字符数为 cnt 时的 LCS 最大长度。 更严谨的定义 ： dp[i][j][cnt] 表示在 s[ 0..i-1] 和 t[ 0..j-1 ] 中，选取一个公共子序列，满足：该公共子序列的末尾连续禁止字符数为 cnt（cnt=0 表示末尾不是禁止字符），且这个公共子序列是所有满足这个条件的公共子序列中最长的长度。 步骤4：状态转移方程 我们有三种基本操作：不选 s[ i-1]，不选 t[ j-1]，或者当 s[ i-1] == t[ j-1 ] 时选它。 不选 s[ i-1]： dp[i][j][cnt] 可以从 dp[i-1][j][cnt] 继承。 不选 t[ j-1]： dp[i][j][cnt] 可以从 dp[i][j-1][cnt] 继承。 当 s[ i-1] == t[ j-1] 时，设 ch = s[ i-1 ]。 如果 ch 不是禁止字符，那么我们可以从任意 cnt' 的状态转移过来，并且新的末尾连续禁止字符数为 0。 即： dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-1][cnt'] + 1) 对所有 cnt' 成立。 如果 ch 是禁止字符，那么我们需要从某个 cnt' 状态转移，并且新的 cnt = cnt' + 1 <= K。 即：如果 cnt' + 1 <= K，则 dp[i][j][cnt' + 1] = max(dp[i][j][cnt' + 1], dp[i-1][j-1][cnt'] + 1) 。 另外，还需要考虑不将 ch 加入 LCS 的情况，这已经被上面的不选 s[ i-1] 或不选 t[ j-1 ] 覆盖。 初始化 ： dp[0][j][0] = 0 对任意 j 成立，因为没有字符，LCS 为空，末尾连续禁止字符数为 0。 同理 dp[i][0][0] = 0 。 其他状态初始为 -∞ 表示不可达。 步骤5：最终答案 最终答案是 max(dp[n][m][cnt]) 对所有 cnt=0..K 取最大值，其中 n、m 分别是 s 和 t 的长度。 步骤6：复杂度分析 状态数 O(n * m * (K+1))，转移每个状态需要 O(K+1) 时间（因为要枚举 cnt'），总复杂度 O(n * m * (K+1)^2)，在 K 不太大时可接受。 例子演示 s = "aabcc", t = "aacbc", forbidden = {'c'}, K=1。 n=5, m=5。 初始化：所有 dp 为 -∞，dp[ 0][ ][ 0]=0, dp[ ][ 0][ 0 ]=0。 我们逐步计算（简化演示关键步骤）： 当 i=1, j=1, 字符 'a'='a'，'a' 非禁止，可以从 dp[ 0][ 0][ 0] 转移，dp[ 1][ 1][ 0 ]=1。 当 i=2, j=2, 字符 'a'='a' 非禁止，可以从 dp[ 1][ 1][ 0] 转移，得到 dp[ 2][ 2][ 0 ]=2。 当 i=3, j=3, 字符 'b'='c' 不相等，只能从不选转移。 当 i=4, j=4, 字符 'c'='b' 不相等。 当 i=5, j=5, 字符 'c'='c' 相等，是禁止字符。 从 dp[ 4][ 4][ cnt' ] 转移： cnt'=0 时，新 cnt=1<=K，所以 dp[ 5][ 5][ 1]=max(原值, dp[ 4][ 4][ 0 ]+1)。 而 dp[ 4][ 4][ 0] 可能来自之前的匹配 "aab" 和 "aacb" 的 LCS "aab" 长度 3，所以 dp[ 5][ 5][ 1 ]=4。 这个对应的 LCS 是 "aabc"，末尾是 'c'，连续禁止字符数=1，合法。 最终答案是 max(dp[ 5][ 5][ cnt ]) = 4。 小结 这道题是 LCS 的一个有趣变种，增加了对公共子序列内容的限制，通过增加状态维度来跟踪末尾连续禁止字符的个数，从而在转移时确保不违反限制。这种思路可以推广到其他有连续次数限制的 DP 问题中。