线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：允许通配符匹配任意字符） 题目描述 给定两个字符串 s1 和 s2 ，其中 s1 可能包含通配符 '*' ， '*' 可以匹配零个或多个任意字符。要求找出 s2 中与 s1 匹配的最长子序列的长度。注意：匹配必须是连续的，即 s1 中的非通配符字符必须按顺序连续出现在 s2 的某个子序列中，且 '*' 可以匹配任意长度的连续字符（包括空字符）。 示例 输入： s1 = "a*b", s2 = "acccb" 输出： 4 （解释： "a" 匹配 s2 的第一个字符 'a' ， '*' 匹配 "ccc" ， 'b' 匹配最后一个 'b' ，整体匹配 "acccb" ） 输入： s1 = "a*b", s2 = "ab" 输出： 2 （ '*' 匹配空字符串） 解题过程 步骤1：问题分析 本题是带通配符的字符串匹配问题，但要求匹配的是最长连续子序列。通配符 '*' 的灵活性使得匹配可能对应 s2 中多个可能的子序列。动态规划的核心是定义状态和转移方程，考虑通配符的匹配规则。 步骤2：定义状态 设 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符匹配时，已匹配的最长连续子序列的长度。注意：匹配必须连续，即 s1 的字符顺序必须严格匹配 s2 的子序列。 步骤3：状态转移方程 基础情况 ： 若 i = 0 （ s1 为空），则 dp[0][j] = 0 （空模式匹配任意字符串长度为0）。 若 j = 0 （ s2 为空），则只有当 s1 全为 '*' 时可能匹配长度为0，否则为负无穷（表示不匹配）。 通配符 '*' 的匹配规则 ： 当 s1[i-1] == '*' 时， '*' 可以匹配零个或多个字符： 匹配零个字符： dp[i][j] = dp[i-1][j] 匹配多个字符： dp[i][j] = max(dp[i][j], dp[i][j-1]) （通过保留 '*' 继续匹配前一个字符） 综合： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 普通字符匹配 ： 当 s1[i-1] == s2[j-1] 时，当前字符匹配，长度加1： dp[i][j] = dp[i-1][j-1] + 1 否则，当前字符不匹配， dp[i][j] = -inf （但需考虑前序状态，实际中初始化为0并取最大值） 步骤4：初始化与边界处理 初始化 dp[0][j] = 0 （空模式匹配任意前缀长度为0）。 dp[i][0] 需特殊处理：若 s1 的前 i 个字符全为 '*' ，则 dp[i][0] = 0 ，否则为负无穷（表示不匹配）。 步骤5：递推与结果提取 遍历 i 从1到 len(s1) ， j 从1到 len(s2) ，按转移方程计算 dp[i][j] 。最终结果为 max(dp[len(s1)][j]) （对所有 j 取最大值），即 s1 匹配 s2 的某个前缀的最长连续子序列长度。 步骤6：示例验证 以 s1 = "a*b", s2 = "acccb" 为例： 初始化： dp[0][j] = 0 i=1 （ s1[0]='a' ）：匹配 s2 中 'a' 时 dp[1][1]=1 ，其余为0或不匹配。 i=2 （ '*' ）：通过转移方程扩展匹配范围。 i=3 （ 'b' ）：在 s2 的 'b' 处匹配，长度累加。 最终 dp[3][5] = 4 ，匹配子序列为 "acccb" 。 总结 本题通过动态规划处理通配符的灵活性，关键在 '*' 的匹配规则：匹配零个字符时继承上方状态，匹配多个字符时继承左方状态。普通字符需精确匹配并累加长度。最终遍历最后一行取最大值得到答案。