线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：通配符可匹配任意长度子串） 题目描述 给定两个字符串 s1 和 s2 ，其中 s1 可能包含通配符 * ， * 可以匹配任意长度的子串（包括空串）。要求找出 s2 的一个子序列，使得该子序列与 s1 去掉通配符后的字符顺序一致，且通配符匹配的子串在 s2 中连续出现。求匹配成功时 s2 中最长子序列的长度。 示例 输入： s1 = "a*b", s2 = "acccb" 输出： 4 （解释： * 匹配 "ccc" ，子序列 "a" + "ccc" + "b" 在 s2 中连续，但要求是子序列，实际匹配 "a" 、 "ccc" 、 "b" 在 s2 中按顺序出现即可，连续性是针对 * 匹配的部分） 解题步骤 问题分析 通配符 * 可匹配任意长度子串（包括空串），但匹配的部分在 s2 中必须连续。 目标：在 s2 中按顺序匹配 s1 的非通配符字符，并最大化匹配长度。 状态定义 设 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符匹配时， s2 中已匹配的最长子序列长度。 注意： s1 中的通配符不直接参与匹配，而是影响匹配方式。 状态转移方程 当 s1[i-1] 不是通配符时： 若 s1[i-1] == s2[j-1] ，则 dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1) 否则， dp[i][j] = dp[i][j-1] （跳过 s2 的当前字符） 当 s1[i-1] 是通配符 * 时： * 可以匹配 s2 中从当前位置开始的任意长度子串（包括空串）。 转移方式： dp[i][j] = max(dp[i-1][k]) ，其中 k 从 0 到 j （表示 * 匹配 s2 中从 k 到 j 的子串） 优化：可通过维护前缀最大值避免遍历 k 。 初始化 dp[0][j] = 0 （ s1 为空时匹配长度为 0） dp[i][0] = 0 （ s2 为空时无法匹配非空 s1 ） 计算顺序 外层循环遍历 s1 的每个字符，内层循环遍历 s2 的每个字符。 遇到通配符时，使用辅助数组记录前缀最大值以优化计算。 结果提取 最终答案为 dp[len(s1)][len(s2)] ，表示整个 s1 与 s2 匹配的最长子序列长度。 关键点 通配符 * 的匹配需通过遍历所有可能的匹配区间实现，利用动态规划的前缀优化降低复杂度。 重点区分通配符匹配的连续性与子序列的顺序性。