线性动态规划：最长公共子序列的变种——带字符限制的最长公共子序列（进阶版：限制某些字符必须连续出现） 题目描述 给定两个字符串 s1 和 s2 ，以及一个限制字符串 pattern 。要求找到 s1 和 s2 的最长公共子序列（LCS），且该子序列必须包含 pattern 作为连续子串（即 pattern 的字符必须连续出现，不能间隔）。例如： s1 = "abcde" , s2 = "ace" , pattern = "c" ，满足条件的 LCS 是 "ace" （包含连续子串 "c" ）。 若 pattern = "cd" ，则需在 LCS 中连续出现 "cd" ，此时无解（因为 s2 中 "c" 和 e 不连续）。 解题思路 问题拆分 ： 先找到 s1 和 s2 的普通 LCS。 增加约束：LCS 必须连续包含 pattern 。 可转化为在 s1 和 s2 中匹配 pattern ，再扩展匹配位置的前后部分。 动态规划定义 ： 定义三维 DP 数组 dp[i][j][k] ： i ：遍历 s1 的前 i 个字符。 j ：遍历 s2 的前 j 个字符。 k ：表示当前已匹配 pattern 的前 k 个字符（ 0 ≤ k ≤ len(pattern) ）。 状态值：在 s1[0..i-1] 和 s2[0..j-1] 中，匹配了 pattern[0..k-1] 时的最长公共子序列长度。 状态转移 ： Case 1 ： s1[i-1] == s2[j-1] 若当前字符等于 pattern[k] ，则 k 可推进： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + 1) （需 k>0 ）。 若当前字符不等于 pattern[k] ，但 k == len(pattern) （已完整匹配 pattern ），则直接扩展 LCS： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + 1) 。 Case 2 ：字符不匹配时，继承之前状态： 特殊处理 ：当 k == 0 （未匹配任何 pattern 字符）时，仅需计算普通 LCS。 初始化 ： dp[0][j][k] = dp[i][0][k] = -∞ （无效状态，但 k=0 时可设为 0）。 dp[0][0][0] = 0 。 答案提取 ： 最终答案为 dp[len(s1)][len(s2)][len(pattern)] ，若其值小于 len(pattern) 则无解。 示例演示 以 s1 = "abcde" , s2 = "ace" , pattern = "c" 为例： 匹配 pattern="c" ： 当 s1[i]='c' 且 s2[j]='c' 时， k 从 0 推进到 1。 完整匹配后，继续扩展前后字符（如 "a" 和 "e" ）。 最终 LCS 为 "ace" ，包含连续子串 "c" ，长度为 3。 复杂度分析 时间复杂度：O(n·m·p)，其中 n, m, p 分别为 s1 , s2 , pattern 的长度。 空间复杂度：可优化至 O(m·p) 使用滚动数组。 关键点 通过 k 维度控制 pattern 的连续匹配进度，确保最终解包含连续 pattern 。 需区分“正在匹配 pattern ”和“已完成匹配”两种状态，后者允许扩展任意字符。