线性动态规划：最长公共子序列的变种——带通配符的最长公共子序列（进阶版：通配符可匹配任意长度子串）

题目描述
给定两个字符串 s1 和 s2，其中 s2 可能包含通配符 *，它可以匹配任意长度的子串（包括空串）。要求找出 s1 和 s2 的最长公共子序列（LCS），但需满足通配符的匹配规则。例如：

• 输入：s1 = "abcde", s2 = "a*c*e"
• 输出：5（LCS 为 "abcde"，因为 * 可匹配 "b" 和 "d" 之间的子串）。

解题过程

1. 定义状态
   设 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的带通配符的 LCS 长度。

   • i 的范围是 [0, len(s1)]，j 的范围是 [0, len(s2)]。
   • 初始条件：dp[0][j] 和 dp[i][0] 需根据通配符规则初始化。

2. 处理通配符的初始化

   • 若 s2 的开头有连续通配符 *，则 dp[0][j] 可能不为 0（因为 * 可匹配空串）。
     具体规则：
     • dp[0][0] = 0（两个空串的 LCS 长度为 0）。
     • 对于 j >= 1，若 s2[j-1] 是 *，则 dp[0][j] = dp[0][j-1]（通配符匹配空串）；否则 dp[0][j] = -∞（表示不匹配）。
   • 对于 i >= 1，dp[i][0] = 0（s2 为空时只能匹配空串）。

3. 状态转移方程
   考虑 s1[i-1] 和 s2[j-1] 的匹配情况：

   • Case 1: s2[j-1] 是通配符 *
* 可匹配空串、单个字符或任意长子串，因此：

     dp[i][j] = max(
         dp[i][j-1],        // * 匹配空串
         dp[i-1][j],        // * 匹配 s1[i-1] 并继续匹配更长部分
         dp[i-1][j-1] + 1   // * 匹配单个字符 s1[i-1]（可选情况，但已被前两种情况覆盖）
     )
     

     注意：dp[i-1][j] 已隐含了 * 匹配多个字符的情况（通过递归地匹配 s1 的前缀）。

   • Case 2: s2[j-1] 不是通配符
     若 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
     否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])（标准 LCS 的不匹配情况）。

4. 递推顺序与最终结果

   • 按 i 从 1 到 len(s1)，j 从 1 到 len(s2) 顺序递推。
   • 最终结果为 dp[len(s1)][len(s2)]。

5. 示例验证
   以 s1 = "abcde", s2 = "a*c*e" 为例：

   • 初始化后，dp 表首行首列均为 0（因 s2 以 * 开头，dp[0][1] 到 dp[0][5] 均为 0）。
   • 递推后，dp[5][5] = 5，匹配整个 s1。

关键点

• 通配符 * 的匹配通过 dp[i][j-1]（匹配空）和 dp[i-1][j]（匹配多个字符）覆盖。
• 时间复杂度 O(nm)，空间复杂度可优化至 O(min(n, m))。