线性动态规划：最长公共子序列的变种——带限制的最长公共子序列（限制子序列必须包含某个特定子串） 题目描述 给定三个字符串 text1 、 text2 和 pattern ，要求找出 text1 和 text2 的最长公共子序列（LCS），但该公共子序列必须包含 pattern 作为其子串。例如，若 text1 = "abcde" ， text2 = "ace" ， pattern = "c" ，则包含 "c" 的 LCS 是 "ace" （因为 "ace" 是公共子序列且包含 "c" ）；若 pattern = "cd" ，则包含 "cd" 的 LCS 不存在（因为 text2 中 "c" 和 "d" 不连续）。 解题过程 问题分析 基础 LCS 使用动态规划：定义 dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的 LCS 长度。 新增约束：公共子序列必须完整包含 pattern 。可转化为在 LCS 中匹配 pattern 的子序列问题。 思路：分阶段处理。先找到 text1 和 text2 的公共子序列，并检查是否包含 pattern 。但直接组合会超时，需将约束融入 DP 状态。 状态设计 定义 dp[i][j][k] ：考虑 text1 的前 i 个字符、 text2 的前 j 个字符时，当前已匹配 pattern 的前 k 个字符的 最长公共超序列长度 （即包含 pattern[0:k] 作为子串的公共子序列长度）。 目标：所有 dp[n][m][k] 中满足 k == len(pattern) 的最大值（即完整匹配 pattern ）。 状态转移 当 text1[i-1] == text2[j-1] 时： 若该字符等于 pattern[k] ：可推进模式匹配， dp[i][j][k] 可从 dp[i-1][j-1][k-1] + 1 转移（匹配一个模式字符）。 无论是否匹配模式，都可选择忽略该字符或仅用作公共子序列： dp[i][j][k] 也可从 dp[i-1][j][k] 、 dp[i][j-1][k] 、 dp[i-1][j-1][k] + 1 转移（注意避免重复）。 当字符不相等时：从 dp[i-1][j][k] 或 dp[i][j-1][k] 转移。 需注意：若 k == 0 （尚未匹配任何模式字符），允许从任意位置开始匹配模式。 初始化与边界 dp[0][j][k] = dp[i][0][k] = -inf （无效状态，因为空字符串无法匹配非空模式，除非 k=0 ）。 例外： dp[0][0][0] = 0 （两个空字符串匹配空模式）。 若 k > 0 且 i=0 或 j=0 ，设为负无穷表示不可能。 算法实现 遍历 i 从 0 到 n ， j 从 0 到 m ， k 从 0 到 len(pattern) 。 对每个状态，根据字符是否相等和模式匹配情况更新。 最终答案： max{ dp[n][m][len(pattern)] } ，若为负无穷则返回 -1 （无解）。 示例验证 设 text1 = "abcde" , text2 = "ace" , pattern = "c" ： 最终 dp[5][3][1] 对应序列 "ace" ，长度为 3，且包含 "c" ，符合要求。 通过此方法，将模式匹配约束嵌入 LCS 的 DP 状态，确保最优解包含目标子串。